package com.my.leetcode;

import java.util.*;
import java.util.stream.Collectors;

public class DynamicProblems {

    public static void main(String[] args) {


        DynamicProblems dynamicProblems = new DynamicProblems();

        int [] a = {9,1,2,3,9};
       // System.out.println(dynamicProblems.largestSumOfAverages(a, 3));

        /*int n = 2;
        int [] rollMax = {1,1,2,2,2,3};
        System.out.println(dynamicProblems.dieSimulator(2, rollMax));
        int [] rollMax2 = {1,1,1,2,2,3};
        System.out.println(dynamicProblems.dieSimulator(3, rollMax2));*/

        char a1 = 'a';
        char d1 = 'd';
        System.out.println(a1 + d1);

    }


    /**
     * @author zlx
     * @Description 974. 和可被 K 整除的子数组
     * 给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
     *
     *
     *
     * 示例：
     *
     * 输入：A = [4,5,0,-2,-3,1], K = 5
     * 输出：7
     * 解释：
     * 有 7 个子数组满足其元素之和可被 K = 5 整除：
     * [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
     *
     *
     * 提示：
     *
     * 1 <= A.length <= 30000
     * -10000 <= A[i] <= 10000
     * 2 <= K <= 10000
     * 解法一： sum[i] = A[0] + …… + A[i] 会超时
     * @Date 4/4/21
     * @Param [A, K]
     * @return int
     **/
    public int subarraysDivByK(int[] A, int K) {

        int n = A.length;
        int [] sumA = new int[n+1];
        for(int i = 1;i <= n;i++){
            sumA[i] = sumA[i-1] + A[i-1];
        }
        int count = 0;
        for(int i = 1;i <=n;i++){
            for(int j = i-1;j >= 0;j--){

                if((sumA[i] - sumA[j]) % K == 0){
                    count++;
                }
            }
        }
        return count;
    }

    public int subarraysDivByKII(int[] A, int K) {

        int [] counts = new int[K];
        int sum = 0;
        for(int i = 0;i < A.length;i++){
            sum += A[i];

            int tmp = sum % K;
            if(tmp < 0){
                tmp += K;
            }
            counts[tmp] ++;
        }

        int res = 0;
        for(int i = 0;i < K;i++){

            if(i == 0){
                res += counts[i] + (counts[i] - 1) * counts[i] / 2;
            }else{
                res += (counts[i] - 1) * counts[i] / 2;
            }
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 712. 两个字符串的最小ASCII删除和 middle
     * 给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。
     *
     * 示例 1:
     *
     * 输入: s1 = "sea", s2 = "eat"
     * 输出: 231
     * 解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。
     * 在 "eat" 中删除 "t" 并将 116 加入总和。
     * 结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
     * 示例 2:
     *
     * 输入: s1 = "delete", s2 = "leet"
     * 输出: 403
     * 解释: 在 "delete" 中删除 "dee" 字符串变成 "let"，
     * 将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。
     * 结束时，两字符串都等于 "let"，结果即为 100+101+101+101 = 403 。
     * 如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。
     * 注意:
     *
     * 0 < s1.length, s2.length <= 1000。
     * 所有字符串中的字符ASCII值在[97, 122]之间。
     *
     * 解题思路： 类似于求解最长公共子序列长度，dp[i][j] 表示到s1[0:i],s2[0:j]存在相同子序列，需要删除的最小ASCII值和
     * @Date 2020-12-29
     * @Param [s1, s2]
     * @return int
     **/
    public int minimumDeleteSum(String s1, String s2) {

        int len1 = s1.length(), len2 = s2.length();
        int [][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 1;i <= len1;i++){
            dp[i][0] += dp[i-1][0] + s1.codePointAt(i - 1);
        }

        for(int j = 1;j <= len2;j++){
            dp[0][j] += dp[0][j-1] + s2.codePointAt(j - 1);
        }

        for(int i = 1;i <= len1;i++){
            for(int j = 1;j <= len2;j++){
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i-1][j] + s1.charAt(i - 1), dp[i][j - 1] + s2.charAt(j-1));
                }
            }
        }

        return dp[len1][len2];

    }

    private int threshold = 1000000007;
    /**
     * @author zlx
     * @Description 1223. 掷骰子模拟 middle
     * 有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。
     *
     * 不过我们在使用它时有个约束，就是使得投掷骰子时，连续 掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。
     *
     * 现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。
     *
     * 假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。
     *
     *
     *
     * 示例 1：
     *
     * 输入：n = 2, rollMax = [1,1,2,2,2,3]
     * 输出：34
     * 解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 = 34。
     * 示例 2：
     *
     * 输入：n = 2, rollMax = [1,1,1,1,1,1]
     * 输出：30
     * 示例 3：
     *
     * 输入：n = 3, rollMax = [1,1,1,2,2,3]
     * 输出：181
     *
     *
     * 提示：
     *
     * 1 <= n <= 5000
     * rollMax.length == 6
     * 1 <= rollMax[i] <= 15
     * @Date 2020-12-28
     * @Param [n, rollMax]
     * @return int
     **/
    public int dieSimulator(int n, int[] rollMax) {

        int [][] dp = new int[n + 1][7];
        for(int i = 1;i <= 6;i++){
            for(int j = 1;j <= Math.min(n, rollMax[i-1]);j++) {
                dp[j][i] = 1;
            }
        }

        for(int i = 2;i <= n;i++){
            for(int j = 1;j < 7;j++){
                for(int k = 1; k <= Math.min(rollMax[j-1],i); ++k){
                    for(int l = 1; l <= 6; ++l){
                        if(j == l){continue;}
                        dp[i][j] = (dp[i][j] + dp[i-k][l])%threshold;
                    }
                }
            }
        }

        return Arrays.stream(dp[n]).reduce(0, (a, b) ->((a + b)% threshold));
    }
    
    /**
     * @author zlx
     * @Description 813. 最大平均值和的分组 middle
     * 我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。
     *
     * 注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。
     *
     * 示例:
     * 输入:
     * A = [9,1,2,3,9]
     * K = 3
     * 输出: 20
     * 解释:
     * A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
     * 我们也可以把 A 分成[9, 1], [2], [3, 9].
     * 这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
     * 说明:
     *
     * 1 <= A.length <= 100.
     * 1 <= A[i] <= 10000.
     * 1 <= K <= A.length.
     * 答案误差在 10^-6 内被视为是正确的。
     *
     * dp[i][k] 表示前i个字符被分割成k组，
     * 那么 dp[i][k] = max(dp[j][k-1] + (A[j+1] + …… + A[i])/(i-j))
     * dp(i, 0) = average(0, i)
     *
     *
     * 简化动态方程：dp[i][k] 只和 k-1有关 ，可以只用2个一维数组进行简化，
     * 从后向前进行动态规划，
     * dp[i][k] = max(dp[j][k-1] + average(i, j-1))
     * dp(i, 0) = average(i, n - 1)
     *
     * @Date 2020-12-28
     * @Param [A, K]
     * @return double
     **/
    public double largestSumOfAverages(int[] A, int K) {

        double [] sums = new double[A.length + 1];
        for(int i = 0;i < A.length;i++){
            sums[i + 1] = sums[i] + A[i];
        }
        int n = A.length;
        double [] dp = new double[n];
        for(int i = 0;i < n;i++){
            dp[i] = (sums[n] - sums[i]) / (n - i);
        }

        for(int k = 0; k < K-1;k++){
            for(int i = 0;i < n;i++){
                for(int j = i+1;j < n;j++){
                    dp[i] = Math.max(dp[i], (sums[j] - sums[i])/ (j - i) + dp[j]);
                }

            }
        }
        return dp[0];
    }

   /* public double largestSumOfAverages(int[] A, int K) {
        int N = A.length;
        double[] P = new double[N+1];
        for (int i = 0; i < N; ++i)
            P[i+1] = P[i] + A[i];

        double[] dp = new double[N];
        for (int i = 0; i < N; ++i)
            dp[i] = (P[N] - P[i]) / (N - i);

        for (int k = 0; k < K-1; ++k)
            for (int i = 0; i < N; ++i)
                for (int j = i+1; j < N; ++j)
                    dp[i] = Math.max(dp[i], (P[j]-P[i]) / (j-i) + dp[j]);

        return dp[0];
    }*/



    /**
     * @author zlx
     * @Description 1218. 最长定差子序列 middle
     * 给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：arr = [1,2,3,4], difference = 1
     * 输出：4
     * 解释：最长的等差子序列是 [1,2,3,4]。
     * 示例 2：
     *
     * 输入：arr = [1,3,5,7], difference = 1
     * 输出：1
     * 解释：最长的等差子序列是任意单个元素。
     * 示例 3：
     *
     * 输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
     * 输出：4
     * 解释：最长的等差子序列是 [7,5,3,1]。
     *
     *
     * 提示：
     *
     * 1 <= arr.length <= 10^5
     * -10^4 <= arr[i], difference <= 10^4
     *
     * 动态规划进行求解： dp[i]表示以i结尾的等差子序列最大长度
     * @Date 2020-12-28
     * @Param [arr, difference]
     * @return int
     **/
    public int longestSubsequence(int[] arr, int difference) {

        int res = 1;
        int [] dp = new int [arr.length];
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0;i < arr.length;i++){

            if(map.containsKey(arr[i] - difference)){
                dp[i] = dp[map.get(arr[i] - difference)] + 1;
            }else{
                dp[i] = 1;
            }
            map.put(arr[i], i);
            res = Math.max(res, dp[i]);
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 1139. 最大的以 1 为边界的正方形 middle
     * 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
     *
     *
     *
     * 示例 1：
     *
     * 输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
     * 输出：9
     * 示例 2：
     *
     * 输入：grid = [[1,1,0,0]]
     * 输出：1
     *
     *
     * 提示：
     *
     * 1 <= grid.length <= 100
     * 1 <= grid[0].length <= 100
     * grid[i][j] 为 0 或 1
     * @Date 2020-12-25
     * @Param [grid]
     * @return int
     **/
    public int largest1BorderedSquare(int[][] grid) {

        int m = grid.length, n = grid[0].length;
        //计算水平方向值为1的和
        int [][] rowGrid = new int[m][n+1];
        //计算垂直方向值1的连续和
        int [][] colGrid = new int[m+1][n];
        int max = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(grid[i][j] == 1) {
                    rowGrid[i][j + 1] = rowGrid[i][j] + grid[i][j];
                    colGrid[i + 1][j] = colGrid[i][j] + grid[i][j];
                }
            }
        }
        for(int i = m-1;i >= 0;i--){
            for(int j = n -1;j >= 0;j--){
                if(grid[i][j] == 1){

                    int small = Math.min(rowGrid[i][j + 1], colGrid[i + 1][j]);
                    while (max < small){
                        if(rowGrid[i - small + 1][j+ 1] >= small && colGrid[i + 1][j - small + 1] >= small){
                            max = small;
                        }
                        small --;
                    }
                }
            }
        }

        return max * max;
    }


    /**
     * @author zlx
     * @Description 面试题 17.23. 最大黑方阵
     * 给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
     *
     * 返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
     *
     * 示例 1:
     *
     * 输入:
     * [
     *    [1,0,1],
     *    [0,0,1],
     *    [0,0,1]
     * ]
     * 输出: [1,0,2]
     * 解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
     * 示例 2:
     *
     * 输入:
     * [
     *    [0,1,1],
     *    [1,0,1],
     *    [1,1,0]
     * ]
     * 输出: [0,0,1]
     * 提示：
     *
     * matrix.length == matrix[0].length <= 200
     *  跟 221. 最大正方形 最大的区别，一个是填满的正方形，一个只需要4条边全是0；
     *  解题思路跟 1139. 最大的以 1 为边界的正方形 middle 一样，唯一的区别是还要求起点
     *
     * @Date 2020-12-10
     * @Param [matrix]
     * @return int[]
     **/
    int [][] rowSum;
    int [][] colSum;
    public int[] findSquare(int[][] matrix) {

        if(matrix == null || matrix.length <= 0){
            return null;
        }

        if(matrix.length == 1){
            if(matrix[0][0] == 0){
                return new int [] {0,0,1};
            }else{
                return new int[0];
            }
        }

        int n = matrix.length;
        rowSum = new int[n][n+1];
        colSum = new int[n+1][n];

        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                if(matrix[i][j] == 0) {
                    rowSum[i][j + 1] = rowSum[i][j] + 1;
                    colSum[i + 1][j] = colSum[i][j] + 1;
                }
            }
        }


        int r = 0, c = 0, max = 0;
        for(int i = n - 1;i >=0;i--){
            for(int j = n-1;j >=0;j--){

                if(matrix[i][j] == 0){
                    int small = Math.min(rowSum[i][j+1], colSum[i + 1][j]);
                    while (max <= small){

                        if(rowSum[i - small + 1][j + 1] >= small && colSum[i + 1][j - small + 1] >= small){
                            max = small;
                            r = i - small + 1;
                            c = j - small + 1;
                        }
                        small --;
                    }
                }
            }
        }

        int [] res = {r, c, max};
        return res;

    }

    public int maxSquare(int x, int y){

        int z = Math.min(x, y);
        for(int i = z;i >= 1;i--) {
            if (rowSum[x][y+1] - rowSum[x][y - z] == 0 && rowSum[x - z][y+1] - rowSum[x - z][y - z] == 0
                    && colSum[x+1][y] - colSum[x - z][y] == 0 && colSum[x+1][y-z] - colSum[x - z][y - z] == 0) {
                return i + 1;
            }
        }
        return 1;
    }



    /**
     * @author zlx
     * @Description 1039. 多边形三角剖分的最低得分 middle
     * 给定 N，想象一个凸 N 边多边形，其顶点按顺时针顺序依次标记为 A[0], A[i], ..., A[N-1]。
     *
     * 假设您将多边形剖分为 N-2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 N-2 个三角形的值之和。
     *
     * 返回多边形进行三角剖分后可以得到的最低分。
     *
     *
     * 示例 1：
     *
     * 输入：[1,2,3]
     * 输出：6
     * 解释：多边形已经三角化，唯一三角形的分数为 6。
     * 示例 2：
     *
     *
     *
     * 输入：[3,7,4,5]
     * 输出：144
     * 解释：有两种三角剖分，可能得分分别为：3*7*5 + 4*5*7 = 245，或 3*4*5 + 3*4*7 = 144。最低分数为 144。
     * 示例 3：
     *
     * 输入：[1,3,1,4,1,5]
     * 输出：13
     * 解释：最低分数三角剖分的得分情况为 1*1*3 + 1*1*4 + 1*1*5 + 1*1*1 = 13。
     *
     *
     * 提示：
     *
     * 3 <= A.length <= 50
     * 1 <= A[i] <= 100
     *
     * 解题思路： 自底向上动态规划
     * dp[i][j] 表示A[i] ,A[j]相连时， A[i] 到A[j]的最小三角剖分得分；
     *
     * @Date 2020-12-25
     * @Param [A]
     * @return int
     **/
    public int minScoreTriangulation(int[] A) {

        int n = A.length;
        if(n == 3){
            return A[0] * A[1] * A[2];
        }
        int [][] dp = new int[n][n];
        for(int d = 2;d < n;d++){
            for(int i = 0;i + d < n;i++){
                int j = i + d;
                dp[i][j] = Integer.MAX_VALUE;
                for(int k = i+1;k < j;k++){
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + A[i] * A[k] * A[j] + dp[k][j]);
                }
            }
        }
        return dp[0][n-1];
    }



    public int change(int amount, int[] coins) {

        int [] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0;i < coins.length;i++){

            for(int j = 1;j <= amount;j++){

                if(j >= coins[i]){
                    dp[j] += dp[j - coins[i]];
                }
            }
        }
        return dp[amount];
    }


    /**
     * @author zlx
     * @Description 377. 组合总和 Ⅳ  middle
     * 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
     *
     * 示例:
     *
     * nums = [1, 2, 3]
     * target = 4
     *
     * 所有可能的组合为：
     * (1, 1, 1, 1)
     * (1, 1, 2)
     * (1, 2, 1)
     * (1, 3)
     * (2, 1, 1)
     * (2, 2)
     * (3, 1)
     *
     * 请注意，顺序不同的序列被视作不同的组合。
     *
     * 因此输出为 7。
     * @Date 2020-12-24
     * @Param [nums, target]
     * @return int
     **/
    public int combinationSum4(int[] nums, int target) {

        int [] dp = new int[target + 1];
        dp[0] = 1;
        for(int j = 1;j <= target;j++){

            for(int i = 0;i < nums.length;i++){

                if(nums[i] <= j){
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }


    /**
     * @author zlx
     * @Description 1504. 统计全 1 子矩形 middle
     * 给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：mat = [[1,0,1],
     *             [1,1,0],
     *             [1,1,0]]
     * 输出：13
     * 解释：
     * 有 6 个 1x1 的矩形。
     * 有 2 个 1x2 的矩形。
     * 有 3 个 2x1 的矩形。
     * 有 1 个 2x2 的矩形。
     * 有 1 个 3x1 的矩形。
     * 矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。
     * 示例 2：
     *
     * 输入：mat = [[0,1,1,0],
     *             [0,1,1,1],
     *             [1,1,1,0]]
     * 输出：24
     * 解释：
     * 有 8 个 1x1 的子矩形。
     * 有 5 个 1x2 的子矩形。
     * 有 2 个 1x3 的子矩形。
     * 有 4 个 2x1 的子矩形。
     * 有 2 个 2x2 的子矩形。
     * 有 2 个 3x1 的子矩形。
     * 有 1 个 3x2 的子矩形。
     * 矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。
     * 示例 3：
     *
     * 输入：mat = [[1,1,1,1,1,1]]
     * 输出：21
     * 示例 4：
     *
     * 输入：mat = [[1,0,1],[0,1,0],[1,0,1]]
     * 输出：5
     * 解题思路来源：
     * https://leetcode-cn.com/problems/count-submatrices-with-all-ones/solution/bian-tong-ji-bian-ya-suo-xiang-xi-by-quantum-10/
     * 提示：
     *
     * 1 <= rows <= 150
     * 1 <= columns <= 150
     * 0 <= mat[i][j] <= 1
     * @Date 2020-12-23
     * @Param [mat]
     * @return int
     **/
    public int numSubmat(int[][] mat) {

        int r = mat.length, c = mat[0].length, ans = 0;

        for(int i = 0;i < r;i++){
            //统计
            for(int j = i;j < r;j++){
                int now = 0;
                for(int k = 0;k < c;k++){

                    if(mat[j][k] == 0){
                        now = 0;
                    }else{
                        now = k == 0 ? mat[j][0] : now+1;
                        ans += now;
                    }
                }
            }

            //压缩
            for(int j = r - 1;j > i;j--){
                for(int k = 0;k < c;k++){
                    mat[j][k] = mat[j][k] & mat[j-1][k];
                }
            }
        }
        return ans;

    }



    /**
     * @author zlx
     * @Description 1641. 统计字典序元音字符串的数目 middle
     * 给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
     *
     * 字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
     *
     *
     *
     * 示例 1：
     *
     * 输入：n = 1
     * 输出：5
     * 解释：仅由元音组成的 5 个字典序字符串为 ["a","e","i","o","u"]
     * 示例 2：
     *
     * 输入：n = 2
     * 输出：15
     * 解释：仅由元音组成的 15 个字典序字符串为
     * ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]
     * 注意，"ea" 不是符合题意的字符串，因为 'e' 在字母表中的位置比 'a' 靠后
     * 示例 3：
     *
     * 输入：n = 33
     * 输出：66045
     *
     *
     * 提示：
     *
     * 1 <= n <= 50
     *
     * 解题思路： 动态规划进行求解， dp[i][j]表示以第i个字符作为第j个位置时的不同组合数目， dp[i][j] = sum(dp[0][j-1] + dp[1][j-1]+…… + dp[i-1][j-1]) 然后再进行简化
     * @Date 2020-12-23
     * @Param [n]
     * @return int
     **/
    public int countVowelStrings(int n) {

        int [] dp = new int[n];
        Arrays.fill(dp, 1);

        for(int i = 2;i <= 5;i++){

            int [] tmp = new int[n];
            tmp[0] = 1;
            for(int j = 1;j < n;j++){
                tmp[j] = dp[j-1] + tmp[j-1];
            }

            for(int j = 0;j < n;j++){
                dp[j] = dp[j] + tmp[j];
            }
        }
        return dp[n-1];
    }


    /**
     * @author zlx
     * @Description 338. 比特位计数 middle
     * 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
     *
     * 示例 1:
     *
     * 输入: 2
     * 输出: [0,1,1]
     * 示例 2:
     *
     * 输入: 5
     * 输出: [0,1,1,2,1,2]
     * @Date 2020-12-23
     * @Param [num]
     * @return int[]
     **/
    public int[] countBits(int num) {

        if(num < 0){
            return null;
        }

        if(num == 0){
            return new int [] {0};
        }

        if(num == 1){
            return new int[]{0,1};
        }

        int [] res = new int[num + 1];
        res[0] = 0;
        res[1] = 1;
        for(int i = 2;i < res.length;i++){
            res[i] = res[i%2] + res[i/2];
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 837. 新21点 middle
     * 爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
     *
     * 爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。 抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。 每次抽取都是独立的，其结果具有相同的概率。
     *
     * 当爱丽丝获得不少于 K 分时，她就停止抽取数字。 爱丽丝的分数不超过 N 的概率是多少？
     *
     *
     *
     * 示例 1：
     *
     * 输入：N = 10, K = 1, W = 10
     * 输出：1.00000
     * 说明：爱丽丝得到一张卡，然后停止。
     * 示例 2：
     *
     * 输入：N = 6, K = 1, W = 10
     * 输出：0.60000
     * 说明：爱丽丝得到一张卡，然后停止。
     * 在 W = 10 的 6 种可能下，她的得分不超过 N = 6 分。
     * 示例 3：
     *
     * 输入：N = 21, K = 17, W = 10
     * 输出：0.73278
     *
     *
     * 提示：
     *
     * 0 <= K <= N <= 10000
     * 1 <= W <= 10000
     * 如果答案与正确答案的误差不超过 10^-5，则该答案将被视为正确答案通过。
     * 此问题的判断限制时间已经减少。
     *
     * 解题思路： 动态规划求解
     * dp[x] 表示得分为x时的得胜概率，分数 K<x<=N dp[x] = 1.0, x>K且x>N, dp[x] = 0.0
     * 因此, 当K≤x≤min(N,K+W−1) 时有 dp[x]=1;
     *      当x>min(N,K+W−1) 时有 dp[x]=0;
     * 当x<K 时， dp[x]= (dp[x+1]+dp[x+2]+⋯+dp[x+W])/W
     * ​
     * @Date 2020-12-21
     * @Param [N, K, W]
     * @return double
     **/
    public double new21Game(int N, int K, int W) {

        if(K == 0){
            return 1.0;
        }

        double [] dp = new double[K + W];

        for(int i = K;i <= N && i < K+W;i++){
            dp[i] = 1;
        }

        for(int i = K - 1;i >= 0;i--){
            for(int j = 1;j <= W;j++){
                dp[i] += dp[i + j]/W;
            }
        }
        return dp[0];
    }

    //解法一会超出时间限制
    public double new21GameII(int N, int K, int W){
        if (K == 0) {
            return 1.0;
        }
        double[] dp = new double[K + W];
        for (int i = K; i <= N && i < K + W; i++) {
            dp[i] = 1.0;
        }
        dp[K - 1] = 1.0 * Math.min(N - K + 1, W) / W;
        for (int i = K - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + W + 1] - dp[i + 1]) / W;
        }
        return dp[0];
    }


    /**
     * @author zlx
     * @Description 873. 最长的斐波那契子序列的长度 middle
     * 如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：
     *
     * n >= 3
     * 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
     * 给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。
     *
     * （回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
     *
     *
     *
     * 示例 1：
     *
     * 输入: [1,2,3,4,5,6,7,8]
     * 输出: 5
     * 解释:
     * 最长的斐波那契式子序列为：[1,2,3,5,8] 。
     * 示例 2：
     *
     * 输入: [1,3,7,11,12,14,18]
     * 输出: 3
     * 解释:
     * 最长的斐波那契式子序列有：
     * [1,11,12]，[3,11,14] 以及 [7,11,18] 。
     *
     *
     * 提示：
     *
     * 3 <= A.length <= 1000
     * 1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
     * （对于以 Java，C，C++，以及 C# 的提交，时间限制被减少了 50%）
     *
     *
     * 解题思路： 基于动态规划进行求解， dp[i][j] 表示斐波那契数列
     * @Date 2020-12-18
     * @Param [A]
     * @return int
     **/
    public int lenLongestFibSubseq(int[] A) {

        int [][] dp = new int[A.length - 1][A.length];
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0;i < A.length;i++){
            map.put(A[i], i);
        }

        for(int i = 0;i < dp.length;i++){
            Arrays.fill(dp[i], 2);
        }

        int res = 0;
        for(int i = 1;i < dp.length;i++){
            for(int j = i + 1;j < A.length;j++){
                int z = A[j] - A[i];
                if(map.containsKey(z) && map.get(z) < i){
                    dp[i][j] = dp[map.get(z)][i] + 1;
                }
                res = Math.max(res, dp[i][j]);
            }
        }

        return res >= 3 ? res : 0;
    }


    /**
     * @author zlx
     * @Description 516. 最长回文子序列 middle
     * 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
     *
     *
     *
     * 示例 1:
     * 输入:
     *
     * "bbbab"
     * 输出:
     *
     * 4
     * 一个可能的最长回文子序列为 "bbbb"。
     *
     * 示例 2:
     * 输入:
     *
     * "cbbd"
     * 输出:
     *
     * 2
     * 一个可能的最长回文子序列为 "bb"。
     *
     *
     *
     * 提示：
     *
     * 1 <= s.length <= 1000
     * s 只包含小写英文字母
     *
     * 解题思路： 核心是求解s、s的逆字符串的最长公共子序列
     * @Date 2020-12-17
     * @Param [s]
     * @return int
     **/
    public int longestPalindromeSubseq(String s) {

        String backS = new StringBuilder(s).reverse().toString();
        int [][] dp = new int[s.length() + 1][s.length() + 1];

        for(int i = 0;i < s.length();i++){
            for(int j = 0;j < s.length();j++){

                if(s.charAt(i) == backS.charAt(j)){

                    dp[i + 1][j + 1] = dp[i][j] + 1;
                }else{
                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        return dp[s.length()][s.length()];

    }

    public int maxSubArray(int[] nums) {

        if(nums.length == 1){
            return nums[0];
        }

        int n  = nums.length;
        int [] sum = new int[n+1];
        int dp[] = new int[n];
        Arrays.fill(dp, Integer.MIN_VALUE);
        for(int i = 1;i <= n;i++){
            sum[i] = sum[i-1] + nums[i-1];
        }
        int res = Integer.MIN_VALUE;
        for(int i = 1;i < n;i++){
            for(int j = 0;j < i-1;j++){
                dp[i] = Math.max(dp[i], sum[i] -sum[j]);
            }
            res = Math.min(dp[i], res);
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 413. 等差数列划分 middle
     * 如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
     *
     * 例如，以下数列为等差数列:
     *
     * 1, 3, 5, 7, 9
     * 7, 7, 7, 7
     * 3, -1, -5, -9
     * 以下数列不是等差数列。
     *
     * 1, 1, 2, 5, 7
     *
     *
     * 数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
     *
     * 如果满足以下条件，则称子数组(P, Q)为等差数组：
     *
     * 元素 A[P], A[p + 1], ..., A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
     *
     * 函数要返回数组 A 中所有为等差数组的子数组个数。
     *
     *
     *
     * 示例:
     *
     * A = [1, 2, 3, 4]
     *
     * 返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
     *
     * 解题思路： 基于动态规划局求解
     * @Date 2020-12-17
     * @Param [A]
     * @return int
     **/
    public int numberOfArithmeticSlices(int[] A) {

        if(A == null || A.length < 3){
            return 0;
        }

        int [] dp = new int[A.length];
        int res = 0;
        for(int i = 2;i < A.length;i++){

            if(A[i]- A[i-1] == A[i-1] - A[i-2]){
                dp[i] = dp[i-1] + 1;
            }else{
                dp[i] = 0;
            }
            res += dp[i];
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 1143. 最长公共子序列 middle
     * 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
     *
     * 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
     * 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
     *
     * 若这两个字符串没有公共子序列，则返回 0。
     *
     *
     *
     * 示例 1:
     *
     * 输入：text1 = "abcde", text2 = "ace"
     * 输出：3
     * 解释：最长公共子序列是 "ace"，它的长度为 3。
     * 示例 2:
     *
     * 输入：text1 = "abc", text2 = "abc"
     * 输出：3
     * 解释：最长公共子序列是 "abc"，它的长度为 3。
     * 示例 3:
     *
     * 输入：text1 = "abc", text2 = "def"
     * 输出：0
     * 解释：两个字符串没有公共子序列，返回 0。
     *
     *
     * 提示:
     *
     * 1 <= text1.length <= 1000
     * 1 <= text2.length <= 1000
     * 输入的字符串只含有小写英文字符。
     *
     * @Date 2020-12-17
     * @Param [text1, text2]
     * @return int
     **/
    public int longestCommonSubsequence(String text1, String text2) {

        int len1 = text1.length();
        int len2 = text2.length();
        int  [][] dp = new int[len1 + 1][len2 + 1];
        for(int i = 0;i < len1;i++){
            for(int j = 0;j < len2;j++){
                if(text1.charAt(i) == text2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j] + 1;
                }else{
                    dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i + 1][j]);
                }
            }
        }
        for(int i = 0;i <= len1;i++){
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[len1][len2];

    }


    /**
     * @author zlx
     * @Description 581. 最短无序连续子数组
     * 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
     *
     * 你找到的子数组应是最短的，请输出它的长度。
     *
     * 示例 1:
     *
     * 输入: [2, 6, 4, 8, 10, 9, 15]
     * 输出: 5
     * 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
     * 说明 :
     *
     * 输入的数组长度范围在 [1, 10,000]。
     * 输入的数组可能包含重复元素 ，所以升序的意思是<=
     *
     * 解题思路： 对数组进行排序，排序后数组newNums, newNums[i] != nums[i] 表示需要重新排序，查找开始排序、结束排序的位置即可
     * @Date 2020-12-16
     * @Param [nums]
     * @return int
     **/
    public int findUnsortedSubarray(int[] nums) {

        if(nums == null || nums.length == 0){
            return 0;
        }

        int [] newNums = nums.clone();
        Arrays.sort(nums);
        int start = newNums.length, end = 0;
        for(int i = 0;i < nums.length;i++){

            if(nums[i] != newNums[i]){

                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }

        return (end - start > 0 ? end - start + 1 : 0);
    }


    public int findUnsortedSubarrayII(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }

        Stack<Integer> stack = new Stack<>();

        int l = Integer.MAX_VALUE;
        for(int i = 0;i < nums.length;i++){

            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]){
                l = Math.min(l, stack.peek());
                stack.pop();
            }
            stack.push(i);
        }

        stack = new Stack<>();
        int r = 0;
        for(int j = nums.length - 1;j >= 0;j--){

            while (!stack.isEmpty() && nums[stack.peek()] < nums[j]){
                r = Math.max(j, r);
                stack.pop();
            }
            stack.push(j);
        }

        return (r - l > 0 ? r - l + 1 : 0);
    }

    /**
     * @author zlx
     * @Description 560. 和为K的子数组
     * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
     *
     * 示例 1 :
     *
     * 输入:nums = [1,1,1], k = 2
     * 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
     * 说明 :
     *
     * 数组的长度为 [1, 20,000]。
     * 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
     *
     * 解题思路： dp[i] 是前i个元素， dp[i] - dp[j] = k 的个数， 简单来讲就是求dp[i]-k 的个数
     * @Date 2020-12-16
     * @Param [nums, k]
     * @return int
     **/
    public int subarraySum(int[] nums, int k) {

        if(nums == null || nums.length <= 0){
            return 0;
        }

        int [] dp = new int [nums.length + 1];
        for(int i = 0;i < nums.length;i++){
            dp[i + 1] = dp[i] + nums[i];
        }

        int times = 0;
        for(int i = 1;i < dp.length;i++){

            for(int j = i-1;j >= 0;j--){
                if(dp[i] - dp[j] == k){
                    times ++;
                }
            }
        }
        return times;
    }



    /**
     * @author zlx
     * @Description 1027. 最长等差数列 middle
     * 给定一个整数数组 A，返回 A 中最长等差子序列的长度。
     *
     * 回想一下，A 的子序列是列表 A[i_1], A[i_2], ..., A[i_k] 其中 0 <= i_1 < i_2 < ... < i_k <= A.length - 1。并且如果 B[i+1] - B[i]( 0 <= i < B.length - 1) 的值都相同，那么序列 B 是等差的。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[3,6,9,12]
     * 输出：4
     * 解释：
     * 整个数组是公差为 3 的等差数列。
     * 示例 2：
     *
     * 输入：[9,4,7,2,10]
     * 输出：3
     * 解释：
     * 最长的等差子序列是 [4,7,10]。
     * 示例 3：
     *
     * 输入：[20,1,15,3,10,5,8]
     * 输出：4
     * 解释：
     * 最长的等差子序列是 [20,15,10,5]。
     *
     *
     * 提示：
     *
     * 2 <= A.length <= 2000
     * 0 <= A[i] <= 10000
     *
     * 解题思路： dp[i][j] 表示等差数列最后2个数字是A[i]，A[j]的 等差数列长度；
     * 等差数列最后2位知道，可求出倒数第三位 Z = A[i] * 2 - A[j]
     * 因此 dp[i][j] = dp[z][i] + 1
     * z位A[0]到A[i-1] 之间等于A[z] = Z 的下表
     *
     *
     * @Date 2020-12-09
     * @Param [A]
     * @return int
     **/
    public int longestArithSeqLength(int[] A) {

        if(A.length <= 0){
            return 0;
        }

        int n = A.length;
        int [][] dp = new int[n][n];
        for(int i = 0;i < n;i++){
            Arrays.fill(dp[i], 2);
            //System.out.println(Arrays.toString(dp[i]));
        }

        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for(int i = 0;i < n;i++){
            for(int j = i + 1;j < n;j++){
                int tmp = 2 * A[i] - A[j];
                if(map.containsKey(tmp)){
                    dp[i][j] = dp[map.get(tmp)][i] + 1;
                }
                max = Integer.max(max, dp[i][j]);
            }
            System.out.println(Arrays.toString(dp[i]));
            //此处最最好用<Integer, List<Integer>> map, key是A[i],value是i
            map.put(A[i], i);
        }
        return max;
    }

    /**
     * @author zlx
     * @Description 931. 下降路径最小和 middle
     * 给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。
     *
     * 下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
     *
     *
     *
     * 示例：
     *
     * 输入：[[1,2,3],[4,5,6],[7,8,9]]
     * 输出：12
     * 解释：
     * 可能的下降路径有：
     * [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
     * [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
     * [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
     * 和最小的下降路径是 [1,4,7]，所以答案是 12。
     *
     *
     *
     * 提示：
     *
     * 1 <= A.length == A[0].length <= 100
     * -100 <= A[i][j] <= 100
     * @Date 2020-12-08
     * @Param [A]
     * @return int
     **/
    public int minFallingPathSum(int[][] A) {

        if(A.length == 1){
            return A[0][0];
        }

        int n = A.length;
        int [][] dp = new int [n][n];


        for(int i = 0;i < n;i++){

            for(int j = 0;j < n;j++){

                if(i == 0){
                    dp[i][j] = A[i][j];
                }else{
                    int lastColumn = dp[i-1][j];
                   if(j - 1 >= 0){
                       lastColumn = Math.min(lastColumn, dp[i-1][j - 1]);
                   }

                   if(j + 1 < n){
                       lastColumn = Math.min(lastColumn, dp[i-1][j + 1]);
                   }

                   dp[i][j] = A[i][j] + lastColumn;
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return Arrays.stream(dp[n-1]).min().getAsInt();
    }


    /**
     * @author zlx
     * @Description 714. 买卖股票的最佳时机含手续费 middle
     * 给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
     *
     * 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
     *
     * 返回获得利润的最大值。
     *
     * 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
     *
     * 示例 1:
     *
     * 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
     * 输出: 8
     * 解释: 能够达到的最大利润:
     * 在此处买入 prices[0] = 1
     * 在此处卖出 prices[3] = 8
     * 在此处买入 prices[4] = 4
     * 在此处卖出 prices[5] = 9
     * 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
     * 注意:
     *
     * 0 < prices.length <= 50000.
     * 0 < prices[i] < 50000.
     * 0 <= fee < 50000.
     * @Date 2020-12-01
     * @Param [prices, fee]
     * @return int
     **/
    public int maxProfit(int[] prices, int fee) {
        if(prices.length <= 1){
            return 0;
        }
        //dp[i][0] 表示第i天持有股票的最大收益， dp[i][1]表示第i天不持有股票的最大收益
        int [][] dp = new int[prices.length + 1][2];
        dp[1][0] = -prices[0]-fee;
        dp[1][1] = 0;

        for(int i = 2;i <= prices.length;i++){

            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i - 1] - fee);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i - 1]);
        }

        return Math.max(dp[prices.length][0], dp[prices.length][1]);

    }


    /**
     * @author zlx
     * @Description 剑指 Offer 14- II. 剪绳子 II middle
     *
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
     * 每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，
     * 我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
     *
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
     * 示例 1：
     *
     * 输入: 2
     * 输出: 1
     * 解释: 2 = 1 + 1, 1 × 1 = 1
     * 示例 2:
     *
     * 输入: 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
     *
     *
     * 提示：
     *
     * 2 <= n <= 1000
     *
     *
     * 解题： 和剑指 Offer 14- I. 剪绳子 I 唯一不同在于本题目涉及 “大数越界情况下的求余问题” 。
     * @Date 2020-11-30
     * @Param [n]
     * @return int
     **/
    public int cuttingRope(int n) {

        if(n <= 3){
            return n-1;
        }
        long res=1L;
        int p=(int)1e9+7;
        //贪心算法，优先切三，其次切二
        while(n>4){
            res = res * 3 % p;
            n -= 3;
        }
        //出来循环只有三种情况，分别是n=2、3、4
        return (int)(res * n % p);
    }


    /**
     * @author zlx
     * @Description 698. 划分为k个相等的子集
     * 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
     *
     * 示例 1：
     *
     * 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
     * 输出： True
     * 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
     *
     *
     * 提示：
     *
     * 1 <= k <= len(nums) <= 16
     * 0 < nums[i] < 10000
     * @Date 2020-11-25
     * @Param [nums, k]
     * @return boolean
     **/
    public boolean canPartitionKSubsets(int[] nums, int k) {

        if(nums == null || nums.length < k){
            return false;
        }

        int sum = Arrays.stream(nums).sum();

        if(sum % k != 0){
            return false;
        }
        Arrays.sort(nums);
        int target = sum/k;
        if(nums[nums.length - 1] > target){
            return false;
        }
        int index = nums.length - 1;
        while(index >= 0 && nums[index] == target) {
            k--;
            index--;
        }

        return search(new int[k], index, nums, target);

    }

    private boolean search(int[] groups, int index, int[] nums, int target) {

        if(index < 0){
            return true;
        }

        int v = nums[index --];

        return false;
    }


    /**
     * @author zlx
     * @Description 808. 分汤   middle
     * 有 A 和 B 两种类型的汤。一开始每种类型的汤有 N 毫升。有四种分配操作：
     *
     * 提供 100ml 的汤A 和 0ml 的汤B。
     * 提供 75ml 的汤A 和 25ml 的汤B。
     * 提供 50ml 的汤A 和 50ml 的汤B。
     * 提供 25ml 的汤A 和 75ml 的汤B。
     * 当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为0.25的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。
     *
     * 注意不存在先分配100 ml汤B的操作。
     *
     * 需要返回的值： 汤A先分配完的概率 + 汤A和汤B同时分配完的概率 / 2。
     *
     * 示例:
     * 输入: N = 50
     * 输出: 0.625
     * 解释:
     * 如果我们选择前两个操作，A将首先变为空。对于第三个操作，A和B会同时变为空。对于第四个操作，B将首先变为空。
     * 所以A变为空的总概率加上A和B同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。
     * 注释:
     *
     * 0 <= N <= 10^9。
     * 返回值在 10^-6 的范围将被认为是正确的。
     * @Date 2020-11-24
     * @Param [N]
     * @return double
     **/
    public double soupServings(int N) {

        N = N / 25 + (N % 25 > 0 ? 1: 0);
        if(N > 500){
            return 1.0;
        }

        double [][] dp = new double [N+1][N+1];
        for(int s = 0;s <= 2 * N;s++){

            for(int i = 0;i <= N;i++){

                int j = s - i;
                if(j < 0 || j > N){
                    continue;
                }
                double ans = 0.0;
                if(i == 0)
                    ans = 1.0;

                if(i == 0 && j == 0)
                    ans = 0.5;

                if(i > 0 && j > 0){

                    ans = 0.25 * (dp[M(i-4)][j] + dp[M(i-3)][M(j-1)] + dp[M(i-2)][M(j-2)] + dp[M(i-1)][M(j-3)]);
                }
                dp[i][j] = ans;

            }
        }
        return dp[N][N];
    }

    public int M(int i){
        return i > 0 ? i : 0;
    }

    /**
     * @author zlx
     * @Description 1546. 和为目标值的最大数目不重叠非空子数组数目 middle
     * 给你一个数组 nums 和一个整数 target 。
     *
     * 请你返回 非空不重叠 子数组的最大数目，且每个子数组中数字和都为 target 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,1,1,1,1], target = 2
     * 输出：2
     * 解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 。
     * 示例 2：
     *
     * 输入：nums = [-1,3,5,1,4,2,-9], target = 6
     * 输出：2
     * 解释：总共有 3 个子数组和为 6 。
     * ([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。
     * 示例 3：
     *
     * 输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
     * 输出：3
     * 示例 4：
     *
     * 输入：nums = [0,0,0], target = 0
     * 输出：3
     *
     * dp[i] 表示第i个数字结尾，构成不重叠的目标和的最大数量
     * 提示：
     *
     * 1 <= nums.length <= 10^5
     * -10^4 <= nums[i] <= 10^4
     * 0 <= target Z<= 10^6
     * @Date 2020-11-20
     * @Param [nums, target]
     * @return int
     **/
    public int maxNonOverlapping(int[] nums, int target) {

        if(nums.length == 1){
            return nums[0] == target ? 1 : 0;
        }

        //将存储前i个字符和由数组转为map，减少for循环次数，key 前val个数字之和
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        int sum = 0;
        int n = nums.length;
        int [] dp = new int[n + 1];

        for(int i = 0;i < n;i++){
            sum += nums[i];
            if(map.containsKey(sum - target)){
                dp[i+1] = Math.max(dp[i], dp[map.get(sum - target)] + 1);
            }else{
                dp[i+1] = dp[i];
            }

            map.put(sum, i+1);

        }
        return dp[n];
    }


    //嵌套会超出时间限制
    public int maxNonOverlappingTimeout(int[] nums, int target) {


        if(nums.length == 1){
            return nums[0] == target ? 1 : 0;
        }

        int n = nums.length;
        int [] dp = new int[n + 1];
        int [] sums = new int[n + 1];
        sums[1] = nums[0];
        int sum = nums[0];
        dp[1] = nums[0] == target ? 1 : 0;
        for(int i = 1;i < n;i++){
            sum += nums[i];
            sums[i+1] = sum;
            if(nums[i] == target) {
                dp[i + 1] = dp[i] + 1;
            }else {
                dp[i + 1] = dp[i];
            }
            for(int j = i - 1;j>= 0;j--){
                if(sums[i+1] - sums[j] == target){
                    dp[i+1] = Math.max(dp[i+1], dp[j] + 1);
                    break;
                }
            }

        }
        return dp[n];
    }



    /**
     * @author zlx
     * @Description 计算正方形个数
     * @Date 2020-11-20
     * @Param [matrix]
     * @return int
     **/
    public int countSquares(int[][] matrix) {

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;
        int [][] dp = new int[m][n];
        int count = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){

                if(matrix[i][j] == 1) {
                    if (i == 0 || j == 0) {
                        dp[i][j] = matrix[i][j];
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }

                    count += dp[i][j];
                }
            }
        }

        return count;
    }


    /**
     * @author zlx
     * @Description 1043. 分隔数组以得到最大和
     * 给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。
     *
     * 返回将数组分隔变换后能够得到的元素最大和。
     *
     *
     *
     * 注意，原数组和分隔后的数组对应顺序应当一致，也就是说，你只能选择分隔数组的位置而不能调整数组中的顺序。
     *
     *
     *
     * 示例 1：
     *
     * 输入：arr = [1,15,7,9,2,5,10], k = 3
     * 输出：84
     * 解释：
     * 因为 k=3 可以分隔成 [1,15,7] [9] [2,5,10]，结果为 [15,15,15,9,10,10,10]，和为 84，是该数组所有分隔变换后元素总和最大的。
     * 若是分隔成 [1] [15,7,9] [2,5,10]，结果就是 [1, 15, 15, 15, 10, 10, 10] 但这种分隔方式的元素总和（76）小于上一种。
     * 示例 2：
     *
     * 输入：arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
     * 输出：83
     * 示例 3：
     *
     * 输入：arr = [1], k = 1
     * 输出：1
     *
     *
     * 解题思路： 要想求dp[i],这是数组的前i个数即nums[0,1...i-1],被切了Y-1刀，分割成Y个数组，满足每个数组的个数最大值不超过KK，每个数组的值变成最大值，分割后的最大和
     *  dp[i] = Math.max(dp[i], dp[j] + (i - j) * max);   i-j <=K
     *
     * 提示：
     *
     * 1 <= arr.length <= 500
     * 0 <= arr[i] <= 109
     * 1 <= k <= arr.length
     * @Date 2020-11-19
     * @Param [arr, k]
     * @return int
     **/
    public int maxSumAfterPartitioning(int[] arr, int k) {

        int len = arr.length;
        int [] dp = new int[len + 1];

        for(int i = 0;i <= len;i++){

            int max = dp[i];
            int j = i - 1;
            while ((i - j) <= k && j >= 0){

                max = Math.max(max, arr[j]);
                dp[i] = Math.max(dp[i], dp[j] + (i - j) * max);
                j--;
            }
        }
        return dp[arr.length];
    }
    

    /**
     * @author zlx
     * @Description 221. 最大正方形
     * 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
     *
     *
     * dp[i][j] 表示以i,j结尾的正方形的最大边长
     *
     * 示例：
     *
     * 输入：
     * matrix = [["1","0","1","0","0"],
     *           ["1","0","1","1","1"],
     *           ["1","1","1","1","1"],
     *           ["1","0","0","1","0"]]
     *
     * 输出：4
     * @Date 2020-11-18
     * @Param [matrix]
     * @return int
     **/
    public int maximalSquare(char[][] matrix) {

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }

        if(matrix.length == 1 && matrix[0].length == 1){
            return matrix[0][0] == '1' ? 1 : 0;
        }
        //最大边长
        int maxSide = 0;
        int m = matrix.length, n = matrix[0].length;
        int [][] dp = new int[m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if (matrix[i][j] == '1') {
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }

            }
        }
        return maxSide * maxSide;
    }

    /**
     * @author zlx
     * @Description 646. 最长数对链 middle
     * 给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
     *
     * 现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
     *
     * 给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
     *
     *
     *
     * 示例：
     *
     * 输入：[[1,2], [2,3], [3,4]]
     * 输出：2
     * 解释：最长的数对链是 [1,2] -> [3,4]
     *
     *
     * 提示：
     *
     * 给出数对的个数在 [1, 1000] 范围内。
     * @Date 2020-11-17
     * @Param [pairs]
     * @return int
     **/
    public int findLongestChain(int[][] pairs) {

        if(pairs.length <= 1){
            return 1;
        }
        //核心，先对数组按照start进行升序排列，然后再使用dp
        Arrays.sort(pairs, (a, b)-> a[0] - b[0]);

        int dp [] = new int[pairs.length];
        Arrays.fill(dp, 1);
        int max = 1;
        for(int i = 1;i < pairs.length;i++){

            for(int j = 0;j < i;j++){
                if(pairs[j][1] < pairs[i][0]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }

    /**
     * @author zlx
     * @Description 1654. 到家的最少跳跃次数 middle
     * 有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。
     *
     * 跳蚤跳跃的规则如下：
     *
     * 它可以 往前 跳恰好 a 个位置（即往右跳）。
     * 它可以 往后 跳恰好 b 个位置（即往左跳）。
     * 它不能 连续 往后跳 2 次。
     * 它不能跳到任何 forbidden 数组中的位置。
     * 跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。
     *
     * 给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
     * 输出：3
     * 解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。
     * 示例 2：
     *
     * 输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
     * 输出：-1
     * 示例 3：
     *
     * 输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
     * 输出：2
     * 解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。
     *
     *
     * 提示：
     *
     * 1 <= forbidden.length <= 1000
     * 1 <= a, b, forbidden[i] <= 2000
     * 0 <= x <= 2000
     * forbidden 中所有位置互不相同。
     * 位置 x 不在 forbidden 中。
     * @Date 2020-11-16
     * @Param [forbidden, a, b, x]
     * @return int
     **/
    public int minimumJumps(int[] forbidden, int a, int b, int x) {

        Arrays.fill(dp, Integer.MAX_VALUE);
        for(int f : forbidden){
            dp[f] = -1;
        }
        front = a;
        back = b;
        pos = x;
        jump(0, 0, false);
        return dp[x] == Integer.MAX_VALUE ? -1 : dp[x];

       /* List<Integer> res = new ArrayList<>();
        for(int f : forbidden){
            res.add(f);
        }
        minSteps = Integer.MAX_VALUE;
        dfsJumps(res, a, b, x, 0, true, 0);
        return minSteps == Integer.MAX_VALUE ? -1 : minSteps;*/
    }


    private int [] dp = new int[4001];
    private int front = 0, back = 0, pos;

    /**
     * @author zlx
     * @Description 使用的是非常简单的思路, 递归+缓存遍历过的位置
     * 神奇的一点在于函数体内需要先向左递归再向右递归,而不能相反...
     * 猜测是由于栈深度的限制,如果先向右的话会持续占用太多内存,而先向左则相对来说没有这方面的问题.
     * 链接：https://leetcode-cn.com/problems/minimum-jumps-to-reach-home/solution/java-di-gui-huan-cun-by-blues-19/
     * @Date 2020-11-16
     * @Param [cur, step, tag]
     * @return void
     **/
    public void jump(int cur, int step, boolean tag){

        if(cur < 0 || cur > 4000 || step >= dp[cur]){
            return ;
        }
        dp[cur] = step;
        if(tag){
            jump(cur - back, step + 1, false);
        }
        jump(cur + front, step + 1, true);
    }

    /**
     * @author zlx
     * @Description dfs求解，超出时间限制
     * @Date 2020-11-16
     * @Param
     * @return
     **/
    int minSteps = Integer.MAX_VALUE;
    public void dfsJumps(List<Integer> forbiddens, int a, int b, int x, int start, boolean forward, int step){


        if(start == x){
            minSteps = Math.min(step, minSteps);
            return;
        }
        //6000是因为a,b,forbidden[i] <= 2000
        if(start >= 0 && start <= 6000) {
            if (!forbiddens.contains(start + a)) {
                //防止无限递归
                forbiddens.add(start + a);
                dfsJumps(forbiddens, a, b, x, start + a, true, step + 1);
            }

            if (!forbiddens.contains(start - b) && forward) {
                dfsJumps(forbiddens, a, b, x, start - b, false, step + 1);
            }
        }

    }





    /**
     * @author zlx
     * @Description 1140. 石子游戏 II middle
     * 亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
     *
     * 亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。
     *
     * 在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
     *
     * 游戏一直持续到所有石子都被拿走。
     *
     * 假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
     *
     *
     *
     * 示例：
     *
     * 输入：piles = [2,7,9,4,4]
     * 输出：10
     * 解释：
     * 如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 
     * 如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
     * 所以我们返回更大的 10。 
     *
     * 解题思路：动态规划进行求解，dp[i][j]表示剩余[i : len - 1]堆时，M = j的情况下，先取的人能获得的最多石子数
     *
     * 当2 * M >= len, 可取走全部[i 到 len-1 ] 的所有数据， dp[i][j] = sum(i:len-1)
     * 当2 * M < len,   1 <=j <= 2 *M， 这种情况就是让下一个人取的最少，当前人取j， 下一个人M = Math.max(j, M), 下一个取值为：dp[i+j][Math.max(j, M)]
     * 因此最多能取"： dp[i][M] = Math.max(dp[i][M], sum - dp[i+j][Math.max(j, M)]);
     *
     * 提示：
     *
     * 1 <= piles.length <= 100
     * 1 <= piles[i] <= 10 ^ 4
     * @Date 2020-11-13
     * @Param [piles]
     * @return int
     **/
    public int stoneGameII(int[] piles) {

       int len = piles.length, sum = 0;
       int [][] dp = new int [piles.length][piles.length + 1];

       for(int i = piles.length - 1;i >= 0;i--){
           sum += piles[i];
           for(int M = 1; M <= len;M++){
               if(i + 2 * M >= len){
                   dp[i][M] = sum;
               }else{

                   for(int j = 1;j <= 2 * M;j++){
                       dp[i][M] = Math.max(dp[i][M], sum - dp[i+j][Math.max(j, M)]);
                   }
               }

           }
       }

       return dp[0][1];
    }


    /**
     * @author zlx
     * @Description 877. 石子游戏 middle
     * 亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。
     *
     * 游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
     *
     * 亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
     *
     * 假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。
     *
     *
     *
     * 示例：
     *
     * 输入：[5,3,4,5]
     * 输出：true
     * 解释：
     * 亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。
     * 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
     * 如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
     * 如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
     * 这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。
     *
     * 解题思路：这道题是「486. 预测赢家」的特例。和第 486486 题相比，这道题增加了两个限制条件：
     *
     * 数组的长度是偶数；
     * 数组的元素之和是奇数，所以没有平局。
     * dp[i][j] 表示当剩下的石子堆为下标i到下标j时，当前玩家与另一个玩家的石子数量之差的最大值
     *
     * 提示：
     *
     * 2 <= piles.length <= 500
     * piles.length 是偶数。
     * 1 <= piles[i] <= 500
     * sum(piles) 是奇数。
     * @Date 2020-11-13
     * @Param [piles]
     * @return boolean
     **/
    public boolean stoneGame(int[] piles) {

        if(piles.length == 2){
            return true;
        }

        int [][] dp = new int [piles.length][piles.length];

        for(int i = 0;i < piles.length;i++){
            dp[i][i] = piles[i];
        }

        for(int i = piles.length - 2;i >= 0;i--){

            for(int j = i+1;j < piles.length;j++){
                dp[i][j] = Math.max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]);
            }
        }

        return dp[0][piles.length - 1] > 0;
    }



    /**
     * @author zlx
     * @Description 514. 自由之路 hard
     * 视频游戏“辐射4”中，任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘，并使用表盘拼写特定关键词才能开门。
     *
     * 给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。
     *
     * 最初，ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。
     *
     * 旋转 ring 拼出 key 字符 key[i] 的阶段中：
     *
     * 您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
     * 如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。
     * 示例：
     *
     *
     *
     *
     *
     * 输入: ring = "godding", key = "gd"
     * 输出: 4
     * 解释:
     *  对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。
     *  对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
     *  当然, 我们还需要1步进行拼写。
     *  因此最终的输出是 4。
     * 提示：
     *
     * ring 和 key 的字符串长度取值范围均为 1 至 100；
     * 两个字符串中都只有小写字符，并且均可能存在重复字符；
     * 字符串 key 一定可以由字符串 ring 旋转拼出。
     *
     * /** i到j
     * 如果 j>i最短步数 min(j-i, len-j+i) + 1
     * 如果 j<i最短步数 min(i-j, len-i+j) + 1
     * 总结来算： min(|i-j|, len-|i-j|) + 1
     * dp[i][j] 表示拼出到key中的第i个字符， ring的第j个字符与12:00方向对齐的最少步数（下标均从0开始）。
     *
     * @Date 2020-11-11
     * @Param [ring, key]
     * @return int
     **/
    public int findRotateSteps(String ring, String key) {


        if(ring.length() == 1){

            return key.length();
        }

        Map<Character, List<Integer>> map = new HashMap<>();

        for(int i = 0;i < ring.length();i++){

            List<Integer> index = new ArrayList<>();
            if(map.containsKey(ring.charAt(i))){
                index = map.get(ring.charAt(i));
            }
            index.add(i);
            map.put(ring.charAt(i), index);
        }

        int m = key.length();
        int n = ring.length();
        int dp[][] = new int [m][n];
        for(int i = 0;i < dp.length;i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE / 2);
        }


        for(Integer i : map.get(key.charAt(0))){
            dp[0][i] = Math.min(i, n - i) + 1;
        }

        for(int i = 1;i < dp.length;i++){
            for(int j : map.get(key.charAt(i))){
                for(int k : map.get(key.charAt(i-1))){
                    dp[i][j] = Math.min(dp[i-1][k] + Math.min(Math.abs(j - k), n - Math.abs(j - k)) + 1, dp[i][j]);
                }

            }
        }

        for(int i = 0;i < m;i++){
            System.out.println(Arrays.toString(dp[i]));
        }
        return Arrays.stream(dp[m - 1]).min().getAsInt();


    }

    /**
     * @author zlx
     * @Description 376. 摆动序列
     * 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
     *
     * 例如， [1,7,4, ,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
     *
     * 给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
     *
     * 示例 1:
     *
     * 输入: [1,7,4,9,2,5]
     * 输出: 6
     * 解释: 整个序列均为摆动序列。
     * 示例 2:
     *
     * 输入: [1,17,5,10,13,15,10,5,16,8]
     * 输出: 7
     * 解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
     * 示例 3:
     *
     * 输入: [1,2,3,4,5,6,7,8,9]
     * 输出: 2
     * 进阶:
     * 你能否用 O(n) 时间复杂度完成此题?
     * @Date 2020-11-09
     * @Param [nums]
     * @return int
     **/
    public int wiggleMaxLength(int[] nums) {

        if(nums == null || nums.length <= 0){
            return 0;
        }

        if(nums.length == 1){
            return 1;
        }

        //动态规划求解dp[i][0] i结尾是升序的最大长度  dp[i][1] 以i结尾是降序最大长度
        int dp [][] = new int [nums.length][2];
        for(int i = 0;i < nums.length;i++){
            Arrays.fill(dp[i], 1);
        }

        int max = Integer.MIN_VALUE;
        for(int i = 1;i < nums.length;i++){

            for(int j = 0;j < i;j++){
                if(nums[j] < nums[i]){
                    dp[i][0] = Math.max(dp[j][1] + 1, dp[i][0]);
                }else if(nums[j] > nums[i]){
                    dp[i][1] = Math.max(dp[j][0] + 1, dp[i][1]);
                }
            }

            max = Math.max(max, dp[i][0]);
            max = Math.max(max, dp[i][1]);
        }

        for(int i = 0;i < nums.length;i++){

            System.out.print(dp[i][0] + "   ");
        }

        System.out.println();

        for(int i = 0;i < nums.length;i++){

            System.out.print(dp[i][1] + "   ");
        }

        System.out.println();
        return max;
    }




    /**
     * @author zlx
     * @Description 673. 最长递增子序列的个数 middle
     * 给定一个未排序的整数数组，找到最长递增子序列的个数。
     *
     * 示例 1:
     *
     * 输入: [1,3,5,4,7]
     * 输出: 2
     * 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
     * 示例 2:
     *
     * 输入: [2,2,2,2,2]
     * 输出: 5
     * 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
     * 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。
     *
     * 解题思路： 基于动态规划求解，
     *       dp[i] 以nums[i]结尾的最长子序列长度
     *       count[i] 以nums[i]结尾的最长子序列组合个数
     * @Date 2020-11-05
     * @Param [nums]
     * @return int
     **/
    public int findNumberOfLIS(int[] nums) {

        if(nums == null || nums.length <= 0){
            return 0;
        }

        if(nums.length == 1){
            return 1;
        }


        int [] dp = new int[nums.length];
        int [] counts = new int [nums.length];
        Arrays.fill(dp, 1);
        Arrays.fill(counts, 1);
        int max = 1;
        for(int i = 1;i < nums.length;i++){
            for(int j = i - 1;j >= 0;j--){
                if(nums[i] > nums[j]){
                    //第一次找到
                    if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        counts[i] = counts[j];
                    }else if(dp[i] == dp[j] + 1){
                        //第二次找到
                        counts[i] += counts[j];
                    }
                }
            }

            max = Math.max(dp[i], max);
        }

        System.out.println(Arrays.toString(counts));
        int count = 0;
        int i = 0;
        for(int tmp : dp){
            if(tmp == max){
                count += counts[i];
            }
            i++;
        }
        return count;


    }


    /**
     * @author zlx
     * @Description 1024. 视频拼接
     * 你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
     *
     * 视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
     *
     * 我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
     * 输出：3
     * 解释：
     * 我们选中 [0,2], [8,10], [1,9] 这三个片段。
     * 然后，按下面的方案重制比赛片段：
     * 将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
     * 现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。
     * 示例 2：
     *
     * 输入：clips = [[0,1],[1,2]], T = 5
     * 输出：-1
     * 解释：
     * 我们无法只用 [0,1] 和 [1,2] 覆盖 [0,5] 的整个过程。
     * 示例 3：
     *
     * 输入：clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
     * 输出：3
     * 解释：
     * 我们选取片段 [0,4], [4,7] 和 [6,9] 。
     * 示例 4：
     *
     * 输入：clips = [[0,4],[2,8]], T = 5
     * 输出：2
     * 解释：
     * 注意，你可能录制超过比赛结束时间的视频。
     *
     *
     * 提示：
     *
     * 1 <= clips.length <= 100
     * 0 <= clips[i][0] <= clips[i][1] <= 100
     * 0 <= T <= 100
     * 动态规划求解， dp[i] 表示从[0,i] 需要的最少视频数量
     *              只有当clips任意视屏片段满足： clips[a][0] < i <= clips[]a[1] ， dp[i] = Math.min(dp[i], dp[clips[a][0]] + 1)
     * @Date 2020-11-04
     * @Param [clips, T]
     * @return int
     **/
    public int videoStitching(int[][] clips, int T) {


        int [] dp = new int[T+1];
        Arrays.fill(dp, Integer.MAX_VALUE/2);
        dp[0] = 0;
        for(int j = 1;j <= T;j++){
            for(int i = 0;i < clips.length;i++){
                if(clips[i][0] < j && j <= clips[i][1]){
                    dp[j] = Math.min(dp[j], dp[clips[i][0]] + 1);
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[T] >= Integer.MAX_VALUE / 2 ? -1 : dp[T];
    }


    /**
     * @author zlx
     * @Description 801. 使序列递增的最小交换次数 middle
     * 我们有两个长度相等且不为空的整型数组 A 和 B 。
     *
     * 我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。
     *
     * 在交换过一些元素之后，数组 A 和 B 都应该是严格递增的（数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.length - 1]）。
     *
     * 给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。假设给定的输入总是有效的。
     *
     * 示例:
     * 输入: A = [1,3,5,4], B = [1,2,3,7]
     * 输出: 1
     * 解释:
     * 交换 A[3] 和 B[3] 后，两个数组如下:
     * A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
     * 两个数组均为严格递增的。
     * 注意:
     *
     * A, B 两个数组的长度总是相等的，且长度的范围为 [1, 1000]。
     * A[i], B[i] 均为 [0, 2000]区间内的整数。
     *
     * 解题思路： 基于动态规划进行求解， a1=A[i-1], a2=A[i-2], b1=B[i-1], b2=B[i], s1表示到i-1递增且A[i-1]，B[i-1]未交换， n2表示到i-1递增且A[i-1]，B[i-1]交换, 然后分2中情况分，得到动态方程
     * @Date 2020-11-02
     * @Param [A, B]
     * @return int
     **/
    public int minSwap(int[] A, int[] B) {

        int n1 = 0, s1 = 1;
        for(int i = 1;i < A.length;i++){

            int n2 = Integer.MAX_VALUE, s2 = Integer.MAX_VALUE;
            if (A[i - 1] < A[i] && B[i-1] < B[i]) {
                n2 = Math.min(n2, n1);
                s2 = Math.min(s1+1, s2);
            }

            if(A[i-1] < B[i] && B[i-1] < A[i]){

                n2 = Math.min(n2, s1);
                s2 = Math.min(n1+1, s2);

            }

            n1 = n2;
            s1 = s2;
        }

        return Math.min(n1, s1);

    }


    /**
     * @author zlx
     * @Description 416. 分割等和子集 middle
     * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
     *
     * 注意:
     *
     * 每个数组中的元素不会超过 100
     * 数组的大小不会超过 200
     * 示例 1:
     *
     * 输入: [1, 5, 11, 5]
     *
     * 输出: true
     *
     * 解释: 数组可以分割成 [1, 5, 5] 和 [11].
     *
     *
     * 示例 2:
     *
     * 输入: [1, 2, 3, 5]
     *
     * 输出: false
     *
     * 解释: 数组不能分割成两个元素和相等的子集.
     * 解题私利：动态规划求解
     * @Date 2020-10-28
     * @Param [nums]
     * @return boolean
     **/
    public boolean canPartition(int[] nums) {

        int sum = 0;
        int maxVal = 0;
        for(int num : nums){
            sum += num;
            maxVal = Math.max(maxVal, num);
        }

        if(sum % 2 != 0){
            return false;
        }
        int target = sum / 2;

        if(maxVal > target){
            return false;
        }
        int n = nums.length;
        //dp[i][j] 表示从[0，i]选择0个或多个 和为j
        boolean [][] dp = new boolean[n][target + 1];
        for(int i = 0;i < n;i++){
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for(int i = 1;i < n;i++){
            for(int j = 1;j <= target;j++){

                if(j >= nums[i]){

                    dp[i][j] = dp[i-1][j-nums[i]] | dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
//        for(int i = 0;i < n;i++){
//            System.out.println(Arrays.toString(dp[i]));
//        }
        return dp[n-1][target];
    }


    boolean canPartition = false;
    //dfs会超时timeout
    public void dfsCanPartition(int [] nums, int index, int target, int sum, boolean[] flag){

        if(sum > target || index >= nums.length){
            return ;
        }

        if(sum == target){
            canPartition = true;
            return ;
        }

        for(int i = 0;i < nums.length;i++){
            if(canPartition){
                break;
            }
            if(!flag[i]) {
                flag[i] = true;
                System.out.println("i======" + i + "     sum is:===" + (sum + nums[i]));
                dfsCanPartition(nums, index + 1, target, sum + nums[i], flag);
                flag[i] = false;
            }
        }

    }

    /**
     * @author zlx
     * @Description 1262. 可被三整除的最大和
     * 给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [3,6,5,1,8]
     * 输出：18
     * 解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
     * 示例 2：
     *
     * 输入：nums = [4]
     * 输出：0
     * 解释：4 不能被 3 整除，所以无法选出数字，返回 0。
     * 示例 3：
     *
     * 输入：nums = [1,2,3,4,4]
     * 输出：12
     * 解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。
     *
     * 解题思路：基于动态规划进行求解，dp[i] 表示 current maximum possible sum that sum % 3 = i
     *
     * 提示：
     *
     * 1 <= nums.length <= 4 * 10^4
     * 1 <= nums[i] <= 10^4
     * @Date 2020-10-27
     * @Param [nums]
     * @return int
     **/
    public int maxSumDivThree(int[] nums) {

        int [] dp = new int[] {0, Integer.MIN_VALUE, Integer.MIN_VALUE};

        for(int num : nums){

            int [] dp2 = new int[3];
            for(int i = 0;i < 3;i++){
                dp2[(num + i) % 3] = Math.max(dp[(num + i) % 3], dp[i] + num);
            }
            System.out.println(Arrays.toString(dp2));
            dp = dp2;
        }
        return dp[0];
    }


    /**
     * @author zlx
     * @Description 1186. 删除一次得到子数组最大和 middle
     * 给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。
     *
     * 换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
     *
     * 注意，删除一个元素后，子数组 不能为空。
     *
     * 请看示例：
     *
     * 示例 1：
     *
     * 输入：arr = [1,-2,0,3]
     * 输出：4
     * 解释：我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。
     * 示例 2：
     *
     * 输入：arr = [1,-2,-2,3]
     * 输出：3
     * 解释：我们直接选出 [3]，这就是最大和。
     * 示例 3：
     *
     * 输入：arr = [-1,-1,-1,-1]
     * 输出：-1
     * 解释：最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。
     *      我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。
     *
     *
     *
     * 解题思路：dp[i][j]表示以arr[i]结尾的，已经删除j次的子数组最大值
     * 递推关系：
     * dp[i][j] = Math.max(dp[i - 1][j] + arr[i],dp[i - 1][j - 1]);
     * 面临两种情况：
     * 不删除arr[i]， dp[i - 1][j] + arr[i]
     * 删除arr[i]，dp[i - 1][j - 1]
     * @Date 2020-10-27
     * @Param [arr]
     * @return int
     **/
    public int maximumSum(int[] arr) {

        int n = arr.length;
        int k = 1;
        int [][] dp = new int[n][k + 1];
        int max = arr[0];
        dp[0][0] = arr[0];
        for(int i = 1;i < n;i++){
            dp[i][0] = Math.max(dp[i-1][0] + arr[i], arr[i]);
            max = Math.max(dp[i][0], max);
        }

        for(int i = 1;i < n;i++){
            for(int j = 1;j <= k;j++){
                dp[i][j]= Math.max(dp[i-1][j] + arr[i], dp[i-1][j-1]);
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }


    /**
     * @author zlx
     * @Description 494. 目标和 middle
     * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
     *
     * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
     *
     *
     *
     * 示例：
     *
     * 输入：nums: [1, 1, 1, 1, 1], S: 3
     * 输出：5
     * 解释：
     *
     * -1+1+1+1+1 = 3
     * +1-1+1+1+1 = 3
     * +1+1-1+1+1 = 3
     * +1+1+1-1+1 = 3
     * +1+1+1+1-1 = 3
     *
     * 一共有5种方法让最终目标和为3。
     *
     * 解题思路： 其实也是一个背包问题，可基于此进行求解
     *
     *
     * 提示：
     *
     * 数组非空，且长度不会超过 20 。
     * 初始的数组的和不会超过 1000 。
     * 保证返回的最终结果能被 32 位整数存下。
     * @Date 2020-10-26
     * @Param [nums, S]
     * @return int
     **/
    public int findTargetSumWays(int[] nums, int S) {

        count = 0;
        sum = 0;
        findTarget(nums, S, 0, sum);
        return count;
    }


    /**
     * @author zlx
     * @Description 基于背包问题进行求解 dp[i][j] 表示前i个元素组成和为j的方案数
     *         dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]
     *         可以写成：
     *
     *         dp[i][j+nums[i]] += dp[i-1][j]
     *         dp[i][j-nums[i]] += dp[i-1][j]
     *
     *         由于数组中所有数的和不超过 1000，那么 j 的最小值可以达到 -1000。在很多语言中，是不允许数组的下标为负数的，因此我们需要给 dp[i][j] 的第二维预先增加 1000，即：
     *
     *          dp[i][j+nums[i] + 1000] += dp[i-1][j + 1000]
     *          dp[i][j-nums[i] + 1000] += dp[i-1][j + 1000]
     *
     * @Date 2020-10-26
     * @Param
     * @return
     **/
    public int findTargetByBagProblems(int [] nums, int S){

        int [][] dp = new int[nums.length][2001];
        dp[0][nums[0] + 1000] = 1;
        dp[0][-nums[0] + 1000] = 1;
        for(int i = 1;i < nums.length;i++){

            for(int j = -1000; j <= 1000;j++){

                if(dp[i-1][j + 1000] > 0){

                    dp[i][j + nums[i] + 1000] += dp[i-1][j+1000];
                    dp[i][j - nums[i] + 1000] += dp[i-1][j+1000];
                }
            }
        }
        return S > 1000 ? 0 : dp[nums.length  - 1][S + 1000];

    }

    //基于递归进行求解
    public void findTarget(int [] nums, int target, int index , int sum) {

        if(index == nums.length){
            if(sum == target){
                count++;
            }
        }else{
            findTarget(nums, target, index + 1, sum + nums[index]);
            findTarget(nums, target, index + 1, sum - nums[index]);
        }
    }




    //解法一：基于dfs进行求解，但是会超出时间限制
    int sum = 0;
    List<Integer> row = new ArrayList<>();
    public void findTarget(int [] nums, int target, int next){

        if(row.size() == nums.length){
            int sum = 0;
            for(int s : row){
                sum += s;
            }
            if(sum == target) {
                count++;
            }
            return ;
        }

        if(next >= nums.length){
            return ;
        }

        for(int i = next;i < nums.length;i++){
            for(int j = 0;j < 2;j++){
                if(j == 0){
                    row.add(nums[i]);
                }else{
                    row.add(-nums[i]);
                }
                findTarget(nums, target, i+1);
                row.remove(row.size() - 1);
            }
        }
    }


    /**
     * @author zlx
     * @Description 1049. 最后一块石头的重量 II
     * 有一堆石头，每块石头的重量都是正整数。
     *
     * 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
     *
     * 如果 x == y，那么两块石头都会被完全粉碎；
     * 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
     * 最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
     *
     *
     *
     * 示例：
     *
     * 输入：[2,7,4,1,8,1]
     * 输出：1
     * 解释：
     * 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
     * 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
     * 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
     * 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
     *
     * 解题思路： 背包问题，石头分成2堆，A和B， 为了使最后剩下的石头重量最小，即A-B差值最小，则A、B越接近越好.即求背包容量为 sum/2 的时候能放大最大重量
     * dp[i][j] 表示放入i-1个石头的时候，背包容量为j时的最大重量,
     *
     * dp[i][j]= max(dp[i-1][j], dp[i-1][j-stones[i-1] + stones[i])
     * 提示：
     *
     * 1 <= stones.length <= 30
     * 1 <= stones[i] <= 1000
     * @Date 2020-10-19
     * @Param [stones]
     * @return int
     **/
    public int lastStoneWeightII(int[] stones) {

        int sum = 0;
        for(int stone : stones){
            sum += stone;
        }

        int target = sum/2;
        int [][] dp = new int[stones.length + 1][target + 1];

        System.out.println(target);
        for(int i = 0;i < stones.length;i++){
            int curStone = stones[i];
            for(int j = 1;j <= target;j++){
                if(j >= curStone) {
                    System.out.println("j====" + j + "   i : ===" + i);
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - curStone] + curStone);
                }else{
                    dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);
                }
            }
        }
        return sum - 2 * dp[stones.length][target];
    }

    /**
     * @author zlx
     * @Description 357. 计算各个位数不同的数字个数 middle
     * 给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
     *
     * 示例:
     *
     * 输入: 2
     * 输出: 91
     * 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
     *
     * 基于动态规划进行求解，
     * n=1   有10中不同的取法
     * n=2   十位不能为0， 9种选择，个位也有9中选择， 2位数字共 9*9=81中选择，再加1位数字 10中选择， 9*9+10
     * n=3   百位不能位0，9中选择，十位9中选择，个位8中选择； 再加上2位数、1位数的取法，共  9*9*8 + 9*9 + 10  中选择
     * 同理， 可用此法推出[0, 10^n),各个位数不同的数字；
     * @Date 2020-10-16
     * @Param [n]
     * @return int
     **/
    public int countNumbersWithUniqueDigits(int n) {

        if(n <= 0){
            return 1;
        }
        if(n == 1){
            return 10;
        }
        int dp = 10, temp = 9, k = 9;
        //最多10个不同的数，超过10，一定会出现重复
        for(int i = 2;i <= Math.min(n, 10);i++){
            temp = temp * k;
            dp += temp;
            k--;
        }
        return dp;
    }

    /**
     * @author zlx
     * @Description 1314. 矩阵区域和
     * 给你一个 m * n 的矩阵 mat 和一个整数 K ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
     *
     * i - K <= r <= i + K, j - K <= c <= j + K
     * (r, c) 在矩阵内。
     *
     *
     * 示例 1：
     *
     * 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
     * 输出：[[12,21,16],[27,45,33],[24,39,28]]
     * 示例 2：
     *
     * 输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
     * 输出：[[45,45,45],[45,45,45],[45,45,45]]
     * @Date 2020-10-15
     * @Param [mat, K]
     * @return int[][]
     **/
    public int[][] matrixBlockSum(int[][] mat, int K) {

        int m = mat.length;
        int n = mat[0].length;
        int [][] res = new int [m][n];
        int [][] dp = new int [m + 1][n +1];
        //dp[i][j] 表示 mat[0][0]到 mat[i][j] 的元素和
        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1] + mat[i- 1][j - 1] - dp[i-1][j-1];
            }
        }

        for(int i = 0;i <= m;i++){
            System.out.println(Arrays.toString(dp[i]));
        }
        for(int i = 0;i < m;i++){
            int rStart = Math.max(0, i - K );
            int rEnd = Math.min(i + K, m -1);
            for(int j = 0;j < n;j++){
               int cEnd = Math.min(j+K, n - 1);
               int cStart = Math.max(j - K, 0);
                System.out.println(rStart + ", " + cStart + "      " + rEnd + ", " + cEnd);
                res[i][j] = dp[rEnd + 1][cEnd + 1]
                        - dp[rStart][cEnd + 1]
                        - dp[rEnd + 1][cStart]
                        + dp[rStart][cStart];

            }
            System.out.println();
        }
        return  res;
    }



    /**
     * @author zlx
     * @Description 467. 环绕字符串中唯一的子字符串 middle
     * 把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，所以 s 看起来是这样的："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
     *
     * 现在我们有了另一个字符串 p 。你需要的是找出 s 中有多少个唯一的 p 的非空子串，尤其是当你的输入是字符串 p ，你需要输出字符串 s 中 p 的不同的非空子串的数目。
     *
     * 注意: p 仅由小写的英文字母组成，p 的大小可能超过 10000。
     *
     *
     *
     * 示例 1:
     *
     * 输入: "a"
     * 输出: 1
     * 解释: 字符串 S 中只有一个"a"子字符。
     *
     *
     * 示例 2:
     *
     * 输入: "cac"
     * 输出: 2
     * 解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。.
     *
     *
     * 示例 3:
     *
     * 输入: "zab"
     * 输出: 6
     * 解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。.
     *
     * 解法二： 基于动态规划求解，dp[i] = Math.max(dp[i], k)  k表示到dp[i]的连续次数, 最后求dp的和
     * @Date 2020-10-14
     * @Param [p]
     * @return int
     **/

    public int findSubstringInWraproundStringII(String p) {

        int [] dp = new int[26];
        int k = 1;
        for(int i = 0;i < p.length();i++){

            char cur = p.charAt(i);
            if(i > 0 && isContinous(p.charAt(i - 1), cur)){
                k++;
            }else{
                k = 1;
            }
            dp[cur - 'a'] = Math.max(dp[cur - 'a'], k);
        }

        int res = 0;
        for(int d : dp){
            res += d;
        }
        return res;

    }

    public boolean isContinous(char prev, char cur){

        if(cur == 'a'){
            return prev == 'z';
        }
        return cur == prev + 1;
    }



    /**
     * @author zlx
     * @Description 解法一：基于2次查找求解
     * @Date 2020-10-14
     * @Param [p]
     * @return int
     **/
    public int findSubstringInWraproundString(String p) {

        if(p == null ||p.length() <= 0){
            return 0;
        }
        if(p.length() == 1){
            return 1;
        }

        List<String> res = new ArrayList<>();
        for(int i = 0;i < p.length();i++){

            char tmp = p.charAt(i);
            if(!res.contains(String.valueOf(tmp))){
                res.add(String.valueOf(tmp));
            }
            String tmpStr = String.valueOf(tmp);
            for(int j = i -1;j >= 0;j--){

                char tmpPrev = p.charAt(j);
                if(tmp == 'a'){
                    if(tmpPrev != 'z'){
                        break;
                    }
                }else if(tmp - tmpPrev != 1){
                    break;
                }
                tmp = tmpPrev;
                tmpStr = tmpPrev + tmpStr;

                if(!res.contains(tmpStr)){
                    System.out.println("tmpStr is:=======" + tmpStr);
                    res.add(tmpStr);
                }
            }
        }
        return res.size();
    }

    /**
     * @author zlx
     * @Description 464. 我能赢吗 middle
     * 在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到或超过 100 的玩家，即为胜者。
     *
     * 如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？
     *
     * 例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。
     *
     * 给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？
     *
     * 你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。
     *
     * 示例：
     *
     * 输入：
     * maxChoosableInteger = 10
     * desiredTotal = 11
     *
     * 输出：
     * false
     *
     * 解释：
     * 无论第一个玩家选择哪个整数，他都会失败。
     * 第一个玩家可以选择从 1 到 10 的整数。
     * 如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
     * 第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
     * 同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
     *
     *
     * 解法一： 基于回溯法进行求解
     * @Date 2020-09-21
     * @Param [maxChoosableInteger, desiredTotal]
     * @return boolean
     **/
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {

        if(maxChoosableInteger >= desiredTotal){
            return true;
        }

        if((1+ maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal){
            return false;
        }

        int state [] = new int [maxChoosableInteger + 1];
        Map<String, Boolean> map = new HashMap<>();
        return trackingCanIWin(desiredTotal, state, map);

    }

    public boolean trackingCanIWin(int desiredTotal, int [] state, Map<String, Boolean> map){

        String stateStr = Arrays.toString(state);
        if(map.containsKey(stateStr)){
            return map.get(stateStr);
        }

        for(int i = 1;i < state.length;i++){
            if(state[i] == 0){
                state[i] = 1;
                if(desiredTotal - i <= 0 || !trackingCanIWin(desiredTotal-i, state, map)){
                    map.put(stateStr, true);
                    state[i]=0;
                    return true;
                }
                //赢不了需要回溯
                state[i]=0;
            }
        }
        map.put(stateStr, false);
        return false;
    }


    /**
     * @author zlx
     * @Description 787. K 站中转内最便宜的航班   middle
     * 有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。
     *
     * 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。
     *
     *
     *
     * 示例 1：
     *
     * 输入: 
     * n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
     * src = 0, dst = 2, k = 1
     * 输出: 200
     * 解释: 
     * 城市航班图如下
     *
     *
     * 从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。
     * 示例 2：
     *
     * 输入:
     * n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
     * src = 0, dst = 2, k = 0
     * 输出: 500
     * 解释:
     * 城市航班图如下
     *
     *
     * 从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。
     *
     *
     * 解题思路： 动态规划，设置dp[i][K] 表示src节点到定点i，经过K次中转，最便宜的价格
     * dp[i][K] = min (dp[a][K-1] + directions[a][i])  a从0到n-1
     *
     * 由于答案要求最多经过 k 站中转的最便宜的价格， 因此最后需要选择 dp[dst][0] 到 dp[dst][K] 的最小值
     *
     *
     * 提示：
     *
     * n 范围是 [1, 100]，城市标签从 0 到 n - 1.
     * 航班数量范围是 [0, n * (n - 1) / 2].
     * 每个航班的格式 (src, dst, price).
     * 每个航班的价格范围是 [1, 10000].
     * k 范围是 [0, n - 1].
     * 航班没有重复，且不存在环路
     * @Date 2020-09-16
     * @Param [n, flights, src, dst, K]
     *
     * dp[i][k] 表示src到i，经历k个中转点，最便宜的价格
     * @return int
     **/
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

        int [][] directions = new int [n][n];
        int [][] dp = new int [n][K + 1];

        for(int i = 0;i < directions.length;i++){
            Arrays.fill(directions[i], Integer.MAX_VALUE/2);
            Arrays.fill(dp[i], Integer.MAX_VALUE/2);
        }

        for(int i = 0;i < flights.length;i++){
            directions[flights[i][0]][flights[i][1]] = flights[i][2];
        }

        for(int i = 0;i < n;i++){
            dp[i][0] = directions[src][i];
        }

        for(int j = 1;j <= K;j++){
            for(int i = 0;i < n;i++){
                if(i != src) {
                    System.out.println("i=======" + i);
                    for (int z = 0; z < n; z++) {
                        if(z != i && z != src) {
                            System.out.println("z=======" + z + "    j====" + j);
                            dp[i][j] = Math.min(dp[i][j], dp[z][j - 1] + directions[z][i]);
                        }
                    }
                }
            }
        }
        for(int i = 0;i < n;i++){
            System.out.println(Arrays.toString(directions[i]));
        }

        System.out.println();
        for(int i = 0;i < n;i++){
            System.out.println(Arrays.toString(dp[i]));
        }
        int res = Integer.MAX_VALUE/2;
        for(int i = 0;i <=K;i++){
            res = Math.min(dp[dst][i], res);
        }
        return res < Integer.MAX_VALUE/2 ? res : -1;
    }



    /**
     * @author zlx
     * @Description 1048. 最长字符串链 middle
     * 给出一个单词列表，其中每个单词都由小写英文字母组成。
     *
     * 如果我们可以在 word1 的任何地方添加一个字母使其变成 word2，那么我们认为 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。
     *
     * 词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。
     *
     * 从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。
     *
     *
     *
     *
     * 示例：
     *
     * 输入：["a","b","ba","bca","bda","bdca"]
     * 输出：4
     * 解释：最长单词链之一为 "a","ba","bda","bdca"。
     *
     *
     * 提示：
     *
     * 1 <= words.length <= 1000
     * 1 <= words[i].length <= 16
     * words[i] 仅由小写英文字母组成。
     *
     *
     * 解题思路： 从words中选择出words[i]，组成数组，表示words数组位置可变， 将words数组按照字符串长度从小到大进行排序，dp[i] 表示i结尾的最长字符串链的最大长度
     * @Date 2020-09-15
     * @Param [words]
     * @return int
     **/
    public int longestStrChain(String[] words) {

        if(words == null || words.length <= 0){
            return 0;
        }
        Arrays.sort(words, new StringComparator());
        System.out.println(Arrays.toString(words));
        int max = Integer.MIN_VALUE;

        List<List<Character>> wordsList = new ArrayList<>();
        for(int i= 0;i < words.length;i++){
            wordsList.add(words[i].chars().mapToObj(j -> (char) j).collect(Collectors.toList()));
        }

        int [] dp = new int[words.length];
        Arrays.fill(dp, 1);
        for(int i = 1;i < dp.length;i++){
            for(int j = i - 1; j >=0;j--){
                if(isChain(wordsList, i, j)){
                    dp[i] = Math.max(dp[i], dp[j] +1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        System.out.println(Arrays.toString(dp));
        return max;
    }

    public boolean isChain(List<List<Character>> wordList, int last, int prev){

        List<Character> lastWords = wordList.get(last);
        List<Character> prevWords = wordList.get(prev);

        if(lastWords.size() != prevWords.size() + 1){
            return false;
        }

        for(Character c : prevWords){
            if(!lastWords.contains(c)){
                return false;
            }
        }
        return true;
    }


    class StringComparator implements Comparator<String>{

        @Override
        public int compare(String o1, String o2) {
            //System.out.println(o1 + "   " + o2 + ",");
            return o1.length() - o2.length();
        }
    }



    /**
     * @author zlx
     * @Description  978. 最长湍流子数组 middle
     * 当 A 的子数组 A[i], A[i+1], ..., A[j] 满足下列条件时，我们称其为湍流子数组：
     *
     * 若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；
     * 或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。
     * 也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
     *
     * 返回 A 的最大湍流子数组的长度。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[9,4,2,10,7,8,8,1,9]
     * 输出：5
     * 解释：(A[1] > A[2] < A[3] > A[4] < A[5])
     * 示例 2：
     *
     * 输入：[4,8,12,16]
     * 输出：2
     * 示例 3：
     *
     * 输入：[100]
     * 输出：1
     *
     * 解题思路： 基于动态规划进行求解， dp[0][i] 表示到nums[i]是升序的湍流子数组长度
     *                              dp[1][i] 表示到nums[i]是降序的湍流子数组长度
     * @Date 2020-09-14
     * @Param [A]
     * @return int
     **/
    public int maxTurbulenceSize(int[] A) {

        if(A == null || A.length <= 0){
            return 0;
        }

        if(A.length == 1){
            return 1;
        }

        int [][] dp = new int[2][A.length];
        dp[0][0] = 1;
        dp[1][0] = 1;

        int max = 1;
        for(int i = 1;i < A.length;i++){

            if(A[i] > A[i-1]){
                dp[0][i] = dp[1][i-1] + 1;
            }else{
                dp[0][i] = 1;
            }

            if(A[i] < A[i - 1]){
                dp[1][i] = dp[0][i-1] + 1;
            }else{
                dp[1][i] = 1;
            }

            max = Math.max(Math.max(dp[0][i], dp[1][i]), max);
        }
        return max;
    }


    /**
     * @author zlx
     * @Description 300. 最长上升子序列
     * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
     *
     * 示例:
     *
     * 输入: [10,9,2,5,3,7,101,18]
     * 输出: 4
     * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
     *
     * [4,10,4,3,8,9]  长度3
     * 说明:
     *
     * 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
     *
     * 动态规划： dp[i] 表示以i结尾的子序列的最大长度
     * 你算法的时间复杂度应该为 O(n2) 。
     * @Date 2020-09-09
               * @return int
     **/
    public int lengthOfLIS(int[] nums) {

        if(nums == null || nums.length <= 0){
            return 0 ;
        }

        int [] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        int maxVal = 1;
        for(int i = 1;i < nums.length;i++){
            for(int j = i -1;j >=0;j--){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            maxVal = Math.max(maxVal, dp[i]);

        }
        return maxVal;

    }



    /**
     * @author zlx
     * @Description 486. 预测赢家 middle
     * 给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。
     *
     * 给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[1, 5, 2]
     * 输出：False
     * 解释：一开始，玩家1可以从1和2中进行选择。
     * 如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。
     * 所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。
     * 因此，玩家 1 永远不会成为赢家，返回 False 。
     * 示例 2：
     *
     * 输入：[1, 5, 233, 7]
     * 输出：True
     * 解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
     *      最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。
     *
     *
     * 解题思路一： dp[i][j] 表示当数组剩下的部分为下标i到下标j时，当前玩家与另一个玩家的分数之差的最大值，注意当前玩家不一定是先手。
     * 当i>j 时，没有意义，  dp[i][j] = 0
     * 当i=j 时，只剩下一个数据， dp[i][j] = nums[i]
     * 当i<j时， 玩家可以取nums[i] or nums[j], dp[i][j] = dp[i-1][j]然后轮到另一个玩家在数组剩下的部分选取数字。
     * 在两种方案中，当前玩家会选择最优的方案，使得自己的分数最大化。因此可以得到如下状态转移方程：
     * dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
     * 最后判断  dp[0][length - 1] 的值，如果大于等于0，则先手得分大于或等于后手得分，因此先手成为赢家，否则后手成为赢家。
     *
     *
     * @Date 2020-09-01
     * @Param [nums]
     * @return boolean
     **/


    public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = nums[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][length - 1] >= 0;
    }



    public boolean PredictTheWinnerII(int[] nums) {

        if(nums == null || nums.length <= 0){
            return false;
        }
        if(nums.length == 1){
            return true;
        }

        int sum = 0;
        int n = nums.length;
        int start = 0, end = nums.length - 1;
        int counts = (nums.length + 1) / 2;
        int [][] dp = new int[2][counts + 1];

        dp[0][1] = nums[start];
        dp[1][1] = nums[end];
        int firstStart = 1, firstEnd = n - 1;
        int secondStart = 0, secondEnd = n - 2;

        for(int i : nums){
            sum += i;
        }

        for(int i = 2; i <= counts;i++){
            int tmp = 0;
            if(nums[firstStart] < nums[firstEnd]){
                firstEnd --;
                if(nums[firstStart] < nums[firstEnd]){
                    tmp = nums[firstEnd];
                    firstEnd --;
                }else{
                    tmp = nums[firstStart];
                    firstStart ++;
                }
            }else{
                firstStart ++;
                if(nums[firstStart] < nums[firstEnd]){
                    tmp = nums[firstEnd];
                    firstEnd --;
                }else{
                    tmp = nums[firstStart];
                    firstStart ++;

                }
            }
            System.out.println("tmp:" + tmp);
            dp[0][i] = dp[0][i-1] + tmp;
        }


        for(int i = 2; i <= counts;i++){
            int tmp = 0;
            if(nums[secondStart] < nums[secondEnd]){
                secondEnd --;
                if(nums[secondStart] < nums[secondEnd]){
                    tmp = nums[secondEnd];
                    secondEnd --;

                }else{
                    tmp = nums[secondStart];
                    secondStart ++;

                }
            }else{
                secondStart ++;
                if(nums[secondStart] < nums[secondEnd]){
                    tmp = nums[secondEnd];
                    secondEnd --;

                }else{
                    tmp = nums[secondStart];
                    secondStart ++;
                }
            }

            dp[1][i] = dp[1][i-1] + tmp;
        }


        System.out.println(dp[0][counts]);
        System.out.println(dp[1][counts]);
        int maxScore = Math.max(dp[0][counts], dp[1][counts]);

        System.out.println("maxScore is:====" + maxScore);

        return  maxScore > (sum - maxScore);
    }


    /**
     * @author zlx
     * @Description 647. 回文子串  middle
     * 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
     *
     * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
     *
     *
     *
     * 示例 1：
     *
     * 输入："abc"
     * 输出：3
     * 解释：三个回文子串: "a", "b", "c"
     * 示例 2：
     *
     * 输入："aaa"
     * 输出：6
     * 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
     *
     *
     * 提示：
     *
     * 输入的字符串长度不会超过 1000 。
     *
     * 解法一： 暴力破解法，分别计算字符串 i到j是否为回文串，并保存到HashMap中， 再次遍历，计算回文串的数量
     * 解法二： 中心扩展法，把字符串中的 一个或者相邻两个字符 当作中心，然后通过两个指针 分别向左向右 扩展，并在扩展的过程中记录当前时刻是否具有 回文属性
     *
     * @Date 2020-08-19
     * @Param [s]
     * @return int
     **/
    public int countSubstrings(String s) {

        int result = 0;
        Map<String,Boolean> map = isPalindrome(s);
        System.out.println(map);
        for(int i = 0;i < s.length();i++){
            int res = 1;
            for(int j =0;j < i;j++){
                //System.out.println("key is:----" + (j+ "_" + i));
                if(map.get(j + "_" + i)){
                    res++;
                }
            }
            result += res;
        }
        return result;
    }


    public int countSubstringsII(String s) {

        if(s == null || s.length() <= 0){
            return 0;
        }
        char [] sArray = s.toCharArray();
        int result = 0;
        for(int i = 0;i < s.length();i++){

            result += countNumOfPalindrome(sArray, i, i);
            result += countNumOfPalindrome(sArray, i, i+1);
        }
        return result;
    }

    public int countNumOfPalindrome(char [] s, int start, int end){
        //System.out.println(start + "    end is: " + end);
        int res = 0;
        while (start >= 0 && start < s.length && end >= 0 && end < s.length && s[start] == s[end]){
            start --;
            end ++;
            res++;
        }
        return res;
    }


    public Map<String, Boolean> isPalindrome(String s){

        Map<String, Boolean> res = new HashMap<>();
        for(int i = 0;i < s.length() - 1;i++){
            for(int j = i+1;j < s.length();j++){

                String tmp = s.substring(i,j+1);
                if(judgeIsPalindrome(tmp)){

                    res.put(i+ "_" + j, true);
                }else{
                    res.put(i + "_" + j, false);
                }
            }
        }
        return res;
    }

    /**
     * @author zlx
     * @Description 判断字符串是否为回文串
     * @Date 2020-08-19
     * @Param [s]
     * @return boolean
     **/
    public boolean judgeIsPalindrome(String s){

        int start = 0;
        int end = s.length() - 1;
        while (start < end){
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    

    /**
     * @author zlx
     * @Description 696. 计数二进制子串 easy
     *
     * 给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。
     *
     * 重复出现的子串要计算它们出现的次数。
     *
     * 示例 1 :
     *
     * 输入: "00110011"
     * 输出: 6
     * 解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
     *
     * 请注意，一些重复出现的子串要计算它们出现的次数。
     *
     * 另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
     * 示例 2 :
     *
     * 输入: "10101"
     * 输出: 4
     * 解释: 有4个子串：“10”，“01”，“10”，“01”，它们具有相同数量的连续1和0。
     * 注意：
     *
     * s.length 在1到50,000之间。
     * s 只包含“0”或“1”字符。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/count-binary-substrings
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     *
     * 方法一：按字符分组
     *
     * 我们可以将字符串 ss 按照 00 和 11 的连续段分组，存在 counts 数组中，
     * 例如 s = 00111011s=00111011，可以得到这样的 counts 数组：counts = {2, 3, 1, 2}
     * 这里 counts 数组中两个相邻的数一定代表的是两种不同的字符。假设 counts 数组中两个相邻的数字为 u或者 v，
     * 它们对应着 u 个 0 和 v 个 1，或者 u 个 1 和 v 个 0。
     * 它们能组成的满足条件的子串数目为 min{u,v}，即一对相邻的数字对答案的贡献。
     *
     *
     * @Date 2020-08-10
     * @Param [s]
     * @return int
     **/
    public int countBinarySubstrings(String s) {

        List<Integer> counts = new ArrayList<>();
        int i = 0, n = s.length();

        while (i < n){
            int count = 0;
            char c = s.charAt(i);
            while (i < n && s.charAt(i) == c){
                count++;
                i++;
            }
            counts.add(count);
        }

        System.out.println("res is:----" + counts);
        int res = 0;
        for(int j = 1;j < counts.size();j++){
            res += Math.min(counts.get(j), counts.get(j - 1));
        }

        return res;

    }




    /**
     * @author zlx
     * @Description 1191. K 次串联后最大子数组之和   middle
     * 给你一个整数数组 arr 和一个整数 k。
     *
     * 首先，我们要对该数组进行修改，即把原数组 arr 重复 k 次。
     *
     * 举个例子，如果 arr = [1, 2] 且 k = 3，那么修改后的数组就是 [1, 2, 1, 2, 1, 2]。
     *
     * 然后，请你返回修改后的数组中的最大的子数组之和。
     *
     * 注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
     *
     * 由于 结果可能会很大，所以需要 模（mod） 10^9 + 7 后再返回。
     *
     *
     * 解法一： 遍历数组，dp[i] 表示0-i之间最大子数组之后，但是会超时
     * @Date 2020-08-05
     * @Param [arr, k]
     * @return int
     **/
    public int kConcatenationMaxSum(int[] arr, int k) {

        if(arr == null || arr.length <= 0){
            return 0;
        }
        int n = arr.length;
        int n2 = n * k;
        //int [] arrK = new int[arr.length * k];
        int [] sum = new int[arr.length * k + 1];
//        for(int i = 0;i < n2;i++){
//            arrK[i] = arr[i % n];
//        }
        for(int i = 1;i < sum.length;i++){
            sum[i] = sum[i-1] + arr[(i-1) % n];
        }
        int res = arr[0];
        for(int i = 1;i < n2;i++){
            int dp = arr[i % n];
            for(int j = i-1;j >=0;j--){
                dp = Math.max(dp, sum[i + 1] - sum[j]);
            }
            res = Math.max(res, dp);
        }
        return res >= 0 ? res : 0;
    }

    int modulo = 1000000007;


    /**
     * 解法二：
     * k = 1: max = 最大子串
     * k >= 1:
     * 如果数组和>0：max = 最大后子串 + (k - 2)*数组和 + 最大前子串
     * 如果数组和<=0：max = 最大后子串 + 最大前子串
     * 最后max与最大子串做对比，取最大值
     *
     **/
    public int kConcatenationMaxSumII(int[] arr, int k) {

        int n = arr.length;
        int maxSoFar = arr[0];
        int maxEndingHere = arr[0];
        for(int i = 1; i < n; i++){
            maxEndingHere = Math.max(maxEndingHere + arr[i], arr[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        if(k < 2) return maxSoFar;

        int leftSum = arr[0];
        int rightSum = arr[n - 1];
        int lMax = Math.max(0, arr[0]);
        int rMax = Math.max(0, arr[n-1]);

        for(int i = 1; i < n; i++){
            leftSum += arr[i];
            lMax = Math.max(lMax, leftSum);
        }

        for(int i = n - 2; i >= 0; i--){
            rightSum += arr[i];
            rMax = Math.max(rMax, rightSum);
        }

        int headTailMax = lMax + rMax;

        if(leftSum < 0) return Math.max(maxSoFar, headTailMax);

        else return Math.max(maxSoFar, (int)(headTailMax + ((k - 2) * (long)leftSum) % modulo));

    }


    /**
     * @author zlx
     * @Description 474. 一和零  middle
     * 在计算机界中，我们总是追求用有限的资源获取最大的收益。
     *
     * 现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。
     *
     * 你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
     *
     * 注意:
     *
     * 给定 0 和 1 的数量都不会超过 100。
     * 给定字符串数组的长度不会超过 600。
     * 示例 1:
     *
     * 输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
     * 输出: 4
     *
     * 解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
     * 示例 2:
     *
     * 输入: Array = {"10", "0", "1"}, m = 1, n = 1
     * 输出: 2
     *
     * 解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。
     *
     * 解题思路： 背包问题的变题
     * dp[i][j] 表示有i个0，j个1
     * dp[i][j] = max(1 + dp[i- zeros[k]][j - ones[k]])
     *
     * zeros[k] 表示字符串str[k] 中0的个数， ones[k] 表示字符串str[k]中1的个数
     *
     * 由于每个0，1只能使用一次，所以是有限背包问题，因此，更新dp[i][j] i,j 要从大到小遍历
     *
     * @Date 2020-07-28
     * @Param [strs, m, n]
     * @return int
     **/
    public int findMaxForm(String[] strs, int m, int n) {

        int[][] dp = new int[m + 1][n + 1];
        for(String str : strs){
            int [] res = getOneAndZeroCount(str);
            for(int i = m;i>= res[0];i--){
                for(int j = n;j >= res[1];j--){
                    dp[i][j] = Math.max(dp[i][j], 1 + dp[i - res[0]][j - res[1]]);
                }
            }
        }
        return dp[m][n];
    }

    public int[] getOneAndZeroCount(String str){

        int [] res = new int[2];
        for(int i = 0;i < str.length();i++){
            res[str.charAt(i) - '0'] ++;
        }
        return res;
    }




    /**
     * @author zlx
     * @Description 392. 判断子序列  easy
     * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
     *
     * 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。
     *
     * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
     *
     * 示例 1:
     * s = "abc", t = "ahbgdc"
     *
     * 返回 true.
     *
     * 示例 2:
     * s = "axc", t = "ahbgdc"
     *
     * 返回 false.
     * @Date 2020-07-27
     * @Param [s, t]
     * @return boolean
     **/
    public boolean isSubsequence(String s, String t) {

        if(t == null){
            return false;
        }
        if(s == null || (s.length() == 0 && t.length() == 0)){
            return true;
        }


        int last = -1;
        for(int i = 0;i < s.length();i++){

            char tmp = s.charAt(i);
            int j = last + 1;
            while (j < t.length()){

                if(t.charAt(j) == tmp){
                    last =j;
                    break;
                }
                j++;
            }
            if(j >= t.length()){
                return false;
            }
        }
        return true;
    }


    /**
     * @author zlx
     * @Description 410. 分割数组的最大值 hard
     * 给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
     *
     * 注意:
     * 数组长度 n 满足以下条件:
     *
     * 1 ≤ n ≤ 1000
     * 1 ≤ m ≤ min(50, n)
     * 示例:
     *
     * 输入:
     * nums = [7,2,5,10,8]
     * m = 2
     *
     * 输出:
     * 18
     *
     * 解释:
     * 一共有四种方法将nums分割为2个子数组。
     * 其中最好的方式是将其分为[7,2,5] 和 [10,8]，
     * 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
     *
     * 解题思路： 基于动态规划进行求解，dp[i][j] 表示前i个字符分割成j段得到最大连续子数组和的最小值
     * 获取动态转移方程
     * dp[i][j] = min{max(f[i-k][j-1], sub(k, i))}, k从0到i-1
     * sub(k, i) sum[k]到sum[i]的和
     *
     * @Date 2020-08-04
     * @Param [nums, m]
     * @return int
     **/
    public int splitArray(int[] nums, int m) {
        if(nums == null ||  nums.length <=0 || m <= 0){
            return 0;
        }

        int n = nums.length;
        int [] sum = new int[n+1];
        int [][] dp = new int [n + 1][m + 1];

        for(int i = 1;i <= n;i++){
            sum[i] = sum[i-1] + nums[i-1];
        }
        for(int i = 0;i <= n;i++){
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        for(int i = 1; i <= n;i++){
            for(int j = 1;j<= m;j++){
                if(i < j){
                    dp[i][j] = Integer.MAX_VALUE;
                }else{
                    for(int k = 0;k <= i-1;k++){
                        dp[i][j] = Math.min(Math.max(dp[k][j-1], sum[i] - sum[k]), dp[i][j]);
                    }
                }
            }
        }

        return dp[n][m];
    }





    /**
     * @author zlx
     * @Description
     * @Date 2020-07-23
     * @Param [grid]
     * @return int
     **/
    public int minPathSum(int[][] grid) {

        if(grid == null || (grid.length == 0 && grid[0].length == 0)){
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;

        int [][] dp = new int [rows][cols];
        dp[0][0] = grid[0][0];

        for(int j = 1;j < cols;j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

        for(int i = 1;i < rows;i++){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }

        for(int i = 1;i < rows;i++){
            for(int j = 1;j < rows;j++){
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[rows - 1][cols - 1];

    }


    /**
     * @author zlx
     * @Description 523. 连续的子数组和   middle
     * 给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[23,2,4,6,7], k = 6
     * 输出：True
     * 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
     * 示例 2：
     *
     * 输入：[23,2,6,4,7], k = 6
     * 输出：True
     * 解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
     * @Date 2020-07-20
     *
     * 解题思路： n^2遍历，
     * @Param [nums, k]
     * @return boolean
     **/
    public boolean checkSubarraySum(int[] nums, int k) {

        if(nums == null || nums.length <= 0){
            return false;
        }

        for(int i = 1;i < nums.length;i++){
            int res = nums[i];
            //j从i-1遍历，找到第一串是k的n倍的子串，返回true，否则继续
            for(int j = i-1;j >= 0;j --){
                res += nums[j];
                if((k != 0 && res % k == 0) ||(k == 0 && res == 0)){
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 120. 三角形最小路径和
     * 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
     *
     * 例如，给定三角形：
     *
     * [
     *      [2],
     *     [3,4],
     *    [6,5,7],
     *   [4,1,8,3]
     * ]
     * 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/triangle
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {

        if(triangle == null || triangle.size() <= 0){
            return 0;
        }
        if(triangle.size() == 1){
            return triangle.get(0).get(0);
        }

        List<List<Integer>> dp = new ArrayList<>();
        dp.add(Arrays.asList(triangle.get(0).get(0)));
        int res = dp.get(0).get(0);
        int tmp = 0;
        int minRow = 0;
        for(int i = 1;i < triangle.size();i++){
            minRow = Integer.MAX_VALUE;
            List<Integer> row = triangle.get(i);
            List<Integer> rowDp = new ArrayList<>();

            for(int j = 0;j < row.size();j++){
                if(j == 0){
                    tmp = dp.get(i-1).get(0) + row.get(j);
                }else if(j == row.size() - 1){
                    tmp = dp.get(i-1).get(j-1) + row.get(j);
                }else{
                    tmp = row.get(j) + Math.min(dp.get(i-1).get(j-1), dp.get(i - 1).get(j));
                }
                rowDp.add(tmp);
                minRow = minRow < tmp ? minRow : tmp;
            }
            dp.add(rowDp);

        }
        return minRow;
    }


    /**
     *
     * 139. 单词拆分
     * 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
     *
     * 说明：
     *
     * 拆分时可以重复使用字典中的单词。
     * 你可以假设字典中没有重复的单词。
     * 示例 1：
     *
     * 输入: s = "leetcode", wordDict = ["leet", "code"]
     * 输出: true
     * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
     * 示例 2：
     *
     * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
     * 输出: true
     * 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     *      注意你可以重复使用字典中的单词。
     * 示例 3：
     *
     * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
     * 输出: false
     *
     * 动态规划解题， dp[i] 表示字符串s从0到(i-1) 能否被拆分成若干个在wordDict中的字符， true能，false否
     *
     **/
    public boolean wordBreak(String s, List<String> wordDict) {

        boolean [] dp = new boolean[s.length() + 1];

        dp[0] = true;
        for(int i = 1;i <= s.length();i++){
            for(int j = 0;j < i;j++){

               if(dp[j] && wordDict.contains(s.substring(j, i))){
                   dp[i] = true;
                   break;
               }
            }
        }
        System.out.println("dp----" + Arrays.toString(dp));
        return dp[s.length()];

    }

    /**
     * @author zlx
     * @Description
     * 面试题 17.13. 恢复空格
     * 哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。
     *
     * 注意：本题相对原题稍作改动，只需返回未识别的字符数
     *
     *
     *
     * 示例：
     *
     * 输入：
     * dictionary = ["looked","just","like","her","brother"]
     * sentence = "jesslookedjustliketimherbrother"
     * 输出： 7
     * 解释： 断句后为"jess looked just like tim her brother"，共7个未识别字符。
     * 提示：
     *
     * 0 <= len(sentence) <= 1000
     * dictionary中总字符数不超过 150000。
     * 你可以认为dictionary和sentence中只包含小写字母。
     *
     * 解题思路： 动态规划，利用字典树进行求解
     * dp[i] 表示到i 未识别字符最小长度
     * j从i开始递减，（j，i）能构成在dictionary中存在的字符，dp[i] = Math.max(dp[i], dp[j-1])
     *
     * @Date 2020-07-09
     * @Param [dictionary, sentence]
     * @return int
     **/
    public int respace(String[] dictionary, String sentence) {

        Trie trie = new Trie();
        for(String str : dictionary){
            trie.insert(str);
        }

        int [] dp = new int[sentence.length() + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1;i <= sentence.length();i++){

            dp[i] = dp[i -1] + 1;
            Trie curPos = trie;
            for(int j = i;j >=1;j--){
                int t = sentence.charAt(j - 1) - 'a';
                if(curPos.next[t] == null){
                    break;
                }else if(curPos.next[t].isEnd){
                    dp[i] = Math.min(dp[i], dp[j-1]);
                }
                if(dp[i] == 0){
                    break;
                }
                curPos = curPos.next[t];
            }
        }

        return dp[sentence.length()];

    }

    //字典树
    class Trie{

        public Trie[] next;
        public boolean isEnd;

        public Trie(){
            next = new Trie[26];
            isEnd = false;
        }

        public void insert(String s){

            Trie curPos = this;

            for(int i = s.length() - 1;i >=0;i--){

                int t = s.charAt(i) - 'a';
                if(curPos.next[t] == null){
                    curPos.next[t] = new Trie();
                }
                curPos = curPos.next[t];
            }
            curPos.isEnd = true;
        }
    }


    /**
     * @author zlx
     * @Description
     * 650. 只有两个键的键盘 middle
     * 最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：
     *
     * Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
     * Paste (粘贴) : 你可以粘贴你上一次复制的字符。
     * 给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。输出能够打印出 n 个 'A' 的最少操作次数。
     *
     * 示例 1:
     *
     * 输入: 3
     * 输出: 3
     * 解释:
     * 最初, 我们只有一个字符 'A'。
     * 第 1 步, 我们使用 Copy All 操作。
     * 第 2 步, 我们使用 Paste 操作来获得 'AA'。
     * 第 3 步, 我们使用 Paste 操作来获得 'AAA'。
     * 说明:
     *
     * n 的取值范围是 [1, 1000] 。
     *
     * 解题思路： 本质上是素数的分解
     * @Date 2020-07-08
     * @Param [n]
     * @return int
     **/
    public int minSteps(int n) {


        int res = 0, d = 2;
        while (n > 1){

            while (n % d == 0){

                res += d;
                n /= d;
            }
            d++;
        }
        return res;

//        if(n <= 1){
//            return 0;
//        }
//
//        int [][] dp = new int [2][n + 1];
//        dp[0][0] = 1;
//        dp[0][1] = 0;
//        dp[0][1] = 1;
//        dp[1][1] = 1;
//
//        for(int i = 2; i<= n;i++){
//            dp[0][i] = Math.max(dp[0][i-1], dp[1][i-1]);
//            dp[1][i] = Math.max(dp[0][i-1]+ dp[1][i-2], dp[1][i-1] + dp[0][i-2]);
//
//            if(dp[1][i] == n){
//                return i;
//            }
//        }
//
//        System.out.println(Arrays.toString(dp[0]));
//        System.out.println(Arrays.toString(dp[1]));
//        return n;
    }


    /**
     * 740. 删除与获得点数 medium
     * 给定一个整数数组 nums ，你可以对它进行一些操作。
     *
     * 每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。
     *
     * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
     *
     * 示例 1:
     *
     * 输入: nums = [3, 4, 2]
     * 输出: 6
     * 解释:
     * 删除 4 来获得 4 个点数，因此 3 也被删除。
     * 之后，删除 2 来获得 2 个点数。总共获得 6 个点数。
     * 示例 2:
     *
     * 输入: nums = [2, 2, 3, 3, 3, 4]
     * 输出: 9
     * 解释:
     * 删除 3 来获得 3 个点数，接着要删除两个 2 和 4 。
     * 之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
     * 总共获得 9 个点数。
     * 注意:
     *
     * nums的长度最大为20000。
     * 每个整数nums[i]的大小都在[1, 10000]范围内。
     *
     * 抢劫的变题
     *
     * 解题思路： 基于动态规划进行求解， 构建数组 tmp[i] 表示 数组nums中，nums[j] = i 的个数
     * dp[i] 表示在节点0-i，进行【删除与获得点数】 操作得到的最大值
     *
     * dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i] * i)
     * @param nums
     * @return
     */
    public int deleteAndEarn(int[] nums) {

        if(nums == null || nums.length <= 0){
            return 0;
        }
        int [] tmp = new int[20001];
        int maxVal = Integer.MIN_VALUE;
        for(int i = 0;i < nums.length;i++){
            tmp[nums[i]] ++;
            maxVal = maxVal >= nums[i] ? maxVal : nums[i];
        }

        int [] dp = new int[20001];
        dp[0] = 0;
        dp[1] = tmp[1];
        for(int i = 2;i <= maxVal;i++){
            dp[i] = Math.max(dp[i - 2] + i * tmp[i], dp[i - 1]);
        }
        return dp[maxVal];
    }


    /**
     *
     * 1014. 最佳观光组合 medium
     *
     * 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
     *
     * 一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
     *
     * 返回一对观光景点能取得的最高分。
     *
     *
     *
     * 示例：
     *
     * 输入：[8,1,5,2,6]
     * 输出：11
     * 解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
     *
     *
     * 提示：
     *
     * 2 <= A.length <= 50000
     * 1 <= A[i] <= 1000
     *
     * 解题思路：一般解题思路是： res[j]表示到景点j的最佳评分， 需要0到j-1的最大值；时间复杂度是O(n^2)
     * 简化思路： res[j] = A[i] + A[j] + i -j = A[i] + i  + (A[j] - j), 其中A[j] - j 对 res[j] 来讲是固定值，因此，只需要求解在j点，0到（i-1）A[i] +i 的最大值，简化复杂度为O(n)
     *
     * @param A
     * @return
     */
    public int maxScoreSightseeingPair(int[] A) {

        if(A == null || A.length <= 0){
            return 0;
        }

        int res = Integer.MIN_VALUE;
        int maxA = A[0];
        for(int i = 1;i < A.length;i++){

            maxA = Math.max(A[i- 1] + i - 1, maxA);
            res = Math.max(res, maxA + A[i] -i);
            System.out.println("i---" + i + " max(A[i] + i)=" + maxA + "   max[i]=" + res);
        }
        return res;
    }


    /**
     * @author zlx
     * @desc 96. 不同的二叉搜索树 medium
     * 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
     *
     * 示例:
     *
     * 输入: 3
     * 输出: 5
     * 解释:
     * 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
     *
     *    1         3     3      2      1
     *     \       /     /      / \      \
     *      3     2     1      1   3      2
     *     /     /       \                 \
     *    2     1         2                 3
     *
     *
     *    解题思路：思路
     *
     * 标签：动态规划
     * 假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数，则
     * G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)
     *
     * 当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i，则
     * f(i) = G(i-1)*G(n-i)
     *
     * 综合两个公式可以得到 卡特兰数 公式
     * G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)
     *
     * @date  2020-06-10
     * @param n
     * @return int
     **/
    public int numTrees(int n) {

        //dp[i] 表示i个节点存在的二叉排序树
        int [] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2;i < n+1;i++){
            for(int j = 1;j < i+1;j++){
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }

    //当n=Integer.MAX_VALUE, 卡特兰公式 G(n+1)= 2*(2n + 1)/(n+2) * G(n)
    public int numTreesII(int n) {

        long g = 1l;
        for(int i = 0;i < n;i++){

            g = g * 2 * (2 * i + 1) / (i + 2);
        }
        return (int)g;
    }

    /**
     * @author zlx
     * @desc 面试题46. 把数字翻译成字符串
     * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
     *
     *
     *
     * 示例 1:
     *
     * 输入: 12258
     * 输出: 5
     * 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
     *
     *
     * 提示：

     *
     * 0 <= num < 231
     *
     * 解题思路； 基于动态规划求解，c[i] 表示到第i为，共有几种不同的组成方式 当num[i-1]num[i] <=25,  c[i] = c[i-1]+c[i-2]; 否则 c[i] = c[i-1], 类似与抢劫题
     * @date  2020-06-09
     * @param num
     * @return int
     **/
    public int translateNum(int num) {

        if(num <= 9){
            return 1;
        }
        String input = String.valueOf(num);
        int [] res = new int[input.length()];
        res[0] = 1;
        if(Integer.valueOf(input.substring(0, 2)) <= 25){
            res[1] = 2;
        }else{
            res[1] = 1;
        }


        for(int i = 2;i < input.length();i++){
            if(Integer.valueOf(input.substring(i-1, i)) > 0 && Integer.valueOf(input.substring(i-1, i+1)) <= 25){
                res[i] = res[i - 1] + res[i - 2];
            }else{
                res[i] = res[i-1];
            }
        }
        return res[input.length() - 1];
    }



    /**
     * @author zlx
     * @desc  152. 乘积最大子数组
        给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

        示例 1:

        输入: [2,3,-2,4]
        输出: 6
        解释: 子数组 [2,3] 有最大乘积 6。
        示例 2:

        输入: [-2,0,-1]
        输出: 0
        解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

    * 解题思路： dp[2][len]
     * dp[0][i] 表示到i的最小乘积
     * dp[1][i] 表示到i的最大成绩
     *
     * 关键是当nums[i] < 0,
     * @date  2020-05-27
     * @param nums
     * @return int
     **/
    public int maxProduct(int[] nums) {


        if(nums == null || nums.length <= 0){
            return 0;
        }
        int max = nums[0];
        int [][] dp = new int[2][nums.length];
        dp[0][0] = nums[0];
        dp[1][0] = nums[0];

        for(int i = 1; i < nums.length;i++){

            if(nums[i] < 0){
                int tmp = dp[0][i - 1];
                dp[0][i - 1] = dp[1][i - 1];
                dp[1][i - 1] = tmp;

            }
            dp[0][i] = Math.min(dp[0][i - 1] * nums[i], nums[i]);
            dp[1][i] = Math.max(dp[1][i - 1] * nums[i], nums[i]);

            max = Math.max(dp[1][i], max);

        }
        return max;
    }


    /**
     * @author zlx
     * @desc 983. 最低票价
     * middle
     * 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
     *
     * 火车票有三种不同的销售方式：
     *
     * 一张为期一天的通行证售价为 costs[0] 美元；
     * 一张为期七天的通行证售价为 costs[1] 美元；
     * 一张为期三十天的通行证售价为 costs[2] 美元。
     * 通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张为期 7 天的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
     *
     * 返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。
     *
     *
     *
     * 示例 1：
     *
     * 输入：days = [1,4,6,7,8,20], costs = [2,7,15]
     * 输出：11
     * 解释：
     * 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
     * 在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
     * 在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
     * 在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
     * 你总共花了 $11，并完成了你计划的每一天旅行。
     * 示例 2：
     *
     * 输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
     * 输出：17
     * 解释：
     * 例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
     * 在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
     * 在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。
     * 你总共花了 $17，并完成了你计划的每一天旅行。
     *
     * 解题思路：
     * dp[i] 表示第i天需要的最少钱
     * 当第i天不需要旅游， dp[i] = dp[i-1]
     * 当第i天需要旅游： dp[i] = Math.min(dp[i-1] + costs[0], dp[i-7] + costs[1], dp[i-30] + costs[2]), (前面一天买的一天通行证，第i天继续买一天的通行证；7天通行证到期，继续买7天的通行证；30天通行证到期，继续买30天的通行证)
     *
     * 提示：
     *
     * 1 <= days.length <= 365
     * 1 <= days[i] <= 365
     * days 按顺序严格递增
     * costs.length == 3
     * 1 <= costs[i] <= 1000
     * @date 11:21 2020-05-06
     * @param days
     * @param costs
     * @return int
     **/
    public int mincostTickets(int[] days, int[] costs) {

        int [] dp = new int[days[days.length - 1] + 1];
        int dayIndex = 0;
        for(int i = 1;i < dp.length;i++){

            if(days[dayIndex] != i){
                dp[i] = dp[i -1];
            }else{
                int tmpDay = dp[i-1] + costs[0];
                int tmp7Day = dp[(i - 7) < 0 ? 0 : (i-7)] + costs[1];
                int tmp30Day = dp[(i - 30) < 0 ? 0 : (i-30)] + costs[2];
                dp[i] = Math.min(Math.min(tmp7Day, tmpDay), tmp30Day);
                dayIndex++;
            }
        }

        return dp[dp.length - 1];
    }


    /**
     * @author zlx
     * @desc 面试题 08.11. 硬币
     * 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
     *
     * 示例1:
     *
     *  输入: n = 5
     *  输出：2
     *  解释: 有两种方式可以凑成总金额:
     * 5=5
     * 5=1+1+1+1+1
     * 示例2:
     *
     *  输入: n = 10
     *  输出：4
     *  解释: 有四种方式可以凑成总金额:
     * 10=10
     * 10=5+5
     * 10=5+1+1+1+1+1
     * 10=1+1+1+1+1+1+1+1+1+1
     * @date 2020-04-23
     * @param n
     * @return int
     **/
    public int waysToChange(int n) {

        if(n < 10){
            return 1 + n / 5;
        }

        int [] dp = new int [n + 1];
        int [] coins = {25, 10};
        //因为只有1分         所以0-4只可能有一种方法  所有的硬币都是1分
        //因为只有1分和5分     所以5-9只可能有2种方法  所有的硬币都是1分 1个5分，其他的一分
        //这个for循环 将所有的1 和 5的情况处理完了
        for(int i = 0;i <= n;i++){
            dp[i] = 1 + i / 5;
        }

        for(int i = 0;i < coins.length;i++){
            for(int j = 10;j <= n;j++){
                if(j < coins[i]){
                    continue;
                }
                dp[j] += dp[j - coins[i]];
                dp[j] = dp[j] % 1000000007;
            }
        }
        return dp[n];
    }


    /**
     * 542. 01 矩阵
     * medium
     *
     * 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
     *
     * 两个相邻元素间的距离为 1 。
     *
     * 示例 1:
     * 输入:
     *
     * 0 0 0
     * 0 1 0
     * 0 0 0
     * 输出:
     *
     * 0 0 0
     * 0 1 0
     * 0 0 0
     * 示例 2:
     * 输入:
     *
     * 0 0 0
     * 0 1 0
     * 1 1 1
     * 输出:
     *
     * 0 0 0
     * 0 1 0
     * 1 2 1
     * 注意:
     *
     * 给定矩阵的元素个数不超过 10000。
     * 给定矩阵中至少有一个元素是 0。
     * 矩阵中的元素只在四个方向上相邻: 上、下、左、右。
     *
     * 解题思路： 动态规划求解，二次便利
     **/
    public int[][] updateMatrix(int[][] matrix) {

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return null;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int dp [][] = new int [m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(matrix[i][j] == 0){
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = Integer.MAX_VALUE / 2;
                }
            }
        }
        //第一次遍历，正向遍历，根据相邻左元素、上元素、当前元素，得到当前元素的对应结果
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if (i - 1 >= 0) {
                    dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j]);
                }

                if(j-1 >= 0){
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                }

            }
        }
        //第二次遍历，反向遍历，根据相邻右元素、下元素、当前元素，得到当前元素的对应结果
        for(int i = m - 1;i >= 0;i--){
            for(int j = n - 1;j >= 0;j--){

                if (i + 1 < m) {
                    dp[i][j] = Math.min(dp[i + 1][j] + 1, dp[i][j]);
                }

                if(j + 1 < n){
                    dp[i][j] = Math.min(dp[i][j + 1] + 1, dp[i][j]);
                }

            }
        }

        return dp;
    }


    /**
    * 887. 鸡蛋掉落
     * 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。
     *
     * 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
     *
     * 你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
     *
     * 每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
     *
     * 你的目标是确切地知道 F 的值是多少。
     *
     * 无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
     *
     *
     *
     * 示例 1：
     *
     * 输入：K = 1, N = 2
     * 输出：2
     * 解释：
     * 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
     * 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
     * 如果它没碎，那么我们肯定知道 F = 2 。
     * 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
     * 示例 2：
     *
     * 输入：K = 2, N = 6
     * 输出：3
     * 示例 3：
     *
     * 输入：K = 3, N = 14
     * 输出：4
     *
     *
     * 解题思路： 基于动态规划+二分查找求解
     * dp(K, N), 从X层丢下去， 两种结果，鸡蛋碎了dp(K-1, X-1)；鸡蛋没有碎 dp(K, N-X)
     * dp(K, N) = min(Max(dp(K-1, X-1), dp(K, N-X)))
    **/
    public int superEggDrop(int K, int N) {

        return dpWithBinarySearch(K, N);
    }

    Map<Integer, Integer> memo = new HashMap();

    public int dpWithBinarySearch(int K, int N){

        if(!memo.containsKey(N * 100 + K)){
            int asn;
            if(N == 0){
                asn = 0;
            }else if(K == 1){
                asn = N;
            }else{
                int low = 1, high = N;
                while (low + 1 < high){
                    int middle = (low + high) / 2;
                    int t1 = dpWithBinarySearch(K-1, middle - 1);
                    int t2 = dpWithBinarySearch(K, N-middle);
                    if(t1 < t2){
                        low = middle;
                    }else if(t1 > t2){
                        high = middle;
                    }else{
                        low = high = middle;
                    }
                }
                asn = 1 + Math.min(Math.max(dpWithBinarySearch(K-1, low - 1), dpWithBinarySearch(K, N-low)),
                        Math.max(dpWithBinarySearch(K - 1, high - 1), dpWithBinarySearch(K, N - high)));
            }
            memo.put(N * 100 + K, asn);

        }
        return memo.get(N * 100 + K);

    }


    public int dp(int K, int N) {

        //使用N*100 + K 题目参数1 <= K <= 100，1 <= N <= 10000，这里等价于自己做哈希函数，避免两层字典导致的内存过大，只要保证任一K和N具有唯一的hashKey
        if (!memo.containsKey(N * 100 + K)) {
            int ans;
            if (N == 0)
                ans = 0;
            else if (K == 1)
                ans = N;
            else {
                int lo = 1, hi = N;
                while (lo + 1 < hi) {
                    int x = (lo + hi) / 2;
                    int t1 = dp(K-1, x-1);
                    int t2 = dp(K, N-x);

                    if (t1 < t2)
                        lo = x;
                    else if (t1 > t2)
                        hi = x;
                    else
                        lo = hi = x;
                }

                ans = 1 + Math.min(Math.max(dp(K-1, lo-1), dp(K, N-lo)),
                        Math.max(dp(K-1, hi-1), dp(K, N-hi)));
            }

            memo.put(N * 100 + K, ans);
        }

        return memo.get(N * 100 + K);
    }



    /**
     * @author zlx
     * @desc 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
     *
     * 你可以对一个单词进行如下三种操作：
     *
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     *  
     *
     * 示例 1：
     *
     * 输入：word1 = "horse", word2 = "ros"
     * 输出：3
     * 解释：
     * horse -> rorse (将 'h' 替换为 'r')
     * rorse -> rose (删除 'r')
     * rose -> ros (删除 'e')
     * 示例 2：
     *
     * 输入：word1 = "intention", word2 = "execution"
     * 输出：5
     * 解释：
     * intention -> inention (删除 't')
     * inention -> enention (将 'i' 替换为 'e')
     * enention -> exention (将 'n' 替换为 'x')
     * exention -> exection (将 'n' 替换为 'c')
     * exection -> execution (插入 'u')
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/edit-distance
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @date 21:32 2020-04-06
     * @param word1, word2
     * @return int
     **/
    public int minDistance(String word1, String word2) {


        int m = word1.length();
        int n = word2.length();

        if (n * m == 0)
            return n + m;

        int [][]dp = new int[m + 1][n + 1];

        //
        for(int i = 0;i <= m;i++){
            dp[i][0] = i;
        }

        for(int j = 0;j <= n;j++){
            dp[0][j] = j;
        }


        for(int i = 1;i <= m;i++){
            for(int j = 1;j <= n;j++){
                int top = dp[i-1][j] + 1;
                int left = dp[i][j - 1] + 1;
                int top_left = dp[i-1][j-1];
                if(word1.charAt(i - 1) != word2.charAt(j - 1)){
                    top_left = top_left + 1;
                }
                dp[i][j] = Math.min(Math.min(top, left), top_left);
                /*if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = Math.min(Math.min(top, left) + 1, top_left);
                }else{
                    dp[i][j] = Math.min(Math.min(top, left), top_left) + 1;
                }*/
            }
        }
        return dp[m][n];
    }


    /**
     * easy
     * 面试题 17.16. 按摩师
     * 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
     *
     * 注意：本题相对原题稍作改动
     *
     *
     *
     * 示例 1：
     *
     * 输入： [1,2,3,1]
     * 输出： 4
     * 解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
     * 示例 2：
     *
     * 输入： [2,7,9,3,1]
     * 输出： 12
     * 解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
     * 示例 3：
     *
     * 输入： [2,1,4,5,3,1,1,3]
     * 输出： 12
     * 解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
     * @param nums
     * @return
     */
    public int massage(int[] nums) {

        if(nums == null || nums.length <= 0){
            return 0;
        }
        int [][] dp = new int [2][nums.length];
        //第一个预约
        dp[0][0] = nums[0];
        //不愉悦
        dp[1][0] = 0;

        for(int i = 1;i < nums.length;i++){

            dp[0][i] = Math.max(dp[1][i-1] + nums[i], dp[0][i-1]);
            dp[1][i] = Math.max(dp[1][i-1], dp[0][i-1]);
        }
        return Math.max(dp[0][nums.length - 1], dp[1][nums.length - 1]);
    }

    /**
     * 309. 最佳买卖股票时机含冷冻期
     * 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​
     *
     * 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
     *
     * 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     * 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
     * 示例:
     *
     * 输入: [1,2,3,0,2]
     * 输出: 3
     * 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     *
     * 动态规划四六
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {

        if(prices == null || prices.length <= 1){
            return 0;
        }
        int len = prices.length;
        int [] buy = new int [len + 1];
        int [] sell = new int [len + 1];
        //int [] hold = new int[len];
        int [] reset = new int[len + 1];

        buy[0] = Integer.MIN_VALUE;
        sell[0] = 0;
        reset[0] = 0;

        for(int i = 1; i <= len;i++){

            int priceIndex = i - 1;
            buy[i] = Math.max(buy[i-1], reset[i-1] - prices[priceIndex]);
            sell[i] = Math.max(sell[i-1], buy[i-1] + prices[priceIndex]);
            reset[i] = Math.max(Math.max(reset[i - 1], buy[i-1]), sell[i-1]);
        }
        return Math.max(sell[len], reset[len]);
    }


    int res = 0;
    /**
     *
     * 980. 不同路径 III
     * 在二维网格 grid 上，有 4 种类型的方格：
     *
     * 1 表示起始方格。且只有一个起始方格。
     * 2 表示结束方格，且只有一个结束方格。
     * 0 表示我们可以走过的空方格。
     * -1 表示我们无法跨越的障碍。
     * 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，每一个无障碍方格都要通过一次。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
     * 输出：2
     * 解释：我们有以下两条路径：     *
     * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
     * 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
     * 示例 2：
     * 输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
     * 输出：4
     * 解释：我们有以下四条路径：
     * 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
     * 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
     * 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
     * 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
     * 示例 3：
     *
     * 输入：[[0,1],[2,0]]
     * 输出：0
     * 解释：
     * 没有一条路能完全穿过每一个空的方格一次。
     * 请注意，起始和结束方格可以位于网格中的任意位置。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/unique-paths-iii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param grid
     * @return
     */
    public int uniquePathsIII(int[][] grid) {

        int step = 1;
        int startX = 0, startY = 0;

        int [][] directions = new int[][]{{0,1}, {1,0}, {0,-1}, {-1, 0}};

        for(int i =0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                if(grid[i][j] == 1){
                    startX = i;
                    startY = j;
                }else if(grid[i][j] == 0){
                    step ++;
                }
            }
        }
        dfs(startX, startY, step, grid, directions);
        return res;
    }

    public void dfs(int x, int y, int step, int[][] grid, int[][] directions){

        if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1){
            return ;
        }

        if(grid[x][y] == 2 && step == 0){
            res++;
            return;
        }

        if(grid[x][y] == 2){

            return;
        }

        grid[x][y] = -1;

        for(int i =0;i < 4;i++){
            int tmpX = x + directions[i][0];
            int tmpY = y + directions[i][1];
            dfs(tmpX, tmpY, step - 1, grid, directions);

        }
        grid[x][y] = 0;

    }

    /**
     * 63. 不同路径 II
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     *
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     *
     * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
     *
     *
     *
     * 网格中的障碍物和空位置分别用 1 和 0 来表示。
     *
     * 说明：m 和 n 的值均不超过 100。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/unique-paths-ii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param obstacleGrid
     * @return
     */
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {


        if(obstacleGrid == null || (obstacleGrid.length == 0 && obstacleGrid[0].length == 0)){
            return 0;
        }

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int [][] dp = new int [obstacleGrid.length][obstacleGrid[0].length];
        for(int i = 0;i < m;i ++){
            if(obstacleGrid[i][0] == 1){
                dp[i][0] = 0;
            }else if(i-1 >= 0 && dp[i-1][0] == 0)
                dp[i][0] = 0;
            else
                dp[i][0] = 1;
        }

        for(int j = 0;j < n;j++){
            if(obstacleGrid[0][j] == 1){
                dp[0][j] = 0;
            }else if( j- 1 >= 0 && dp[0][j - 1] == 0){
                dp[0][j] = 0;
            }else{
                dp[0][j] = 1;
            }
        }

        for(int i = 1; i< m; i++){
            for(int j = 1; j< n; j++){

                if(obstacleGrid[i][j] == 1){

                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }

        return dp[m - 1][n - 1];

    }


    /**
     *
     * 62. 不同路径
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     *
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     *
     * 问总共有多少条不同的路径？
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/unique-paths
     *
     *
     * 解题思路： 用动态规划解题， dp[i][j] = dp[i-1][j] + dp[i][j - 1];
     * @param m
     * @param n
     * @return
     */
    public static int uniquePaths(int m, int n) {

        if(m <= 0 && n <= 0){
            return 0;
        }

        int [][] dp = new int [m][n];
        for(int i = 0; i< m; i++){
            dp[i][0] = 1;
        }

        for(int j = 0; j< n;j++){
            dp[0][j] = 1;
        }

        for(int i = 1; i < m;i++){

            for(int j = 1; j < n;j++){

                dp[i][j] = dp[i-1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];

        /*int [][] direction = new int[][]{{0,1},{1,0}};
        dfs(m, n, 0,0, direction);
        System.out.println("result is-------" + count);
        return count;*/

    }

    public static int count = 0;

    public static void dfs(int m, int n, int row, int col, int [][] direction){


        System.out.println("row: =" + row + "   col is: " + col);
        if(row == (m-1) && col == (n - 1)){

            count++;
            System.out.println("equals0--------" + count);
            return;
        }

        for(int i = 0;i < 2;i++){
            if(row + direction[i][0] < m && col + direction[i][1] < n){
                dfs(m, n, row + direction[i][0], col + direction[i][1], direction);
            }else{
                continue;
            }
        }
        return;
    }







    /**
     *
     * 746. Min Cost Climbing Stairs
     *
     *
     * 数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
     *
     * 每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
     *
     * 您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
     *
     * 示例 1:
     *
     * 输入: cost = [10, 15, 20]
     * 输出: 15
     * 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
     *  示例 2:
     *
     * 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
     * 输出: 6
     * 解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
     *
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param cost
     * @return
     */
    public static int minCostClimbingStairs(int[] cost) {

        if(cost == null || cost.length <= 0){
            return 0;
        }
        int [][] dp = new int[2][cost.length];

        dp[0][0] = cost[0];
        dp[0][1] = dp[0][0] + cost[1];

        //dp[0][2] = Math.min(dp[0][1] + cost[2], dp[0][0] + cost[2]);

        for(int i =2;i < cost.length;i++){
            dp[0][i] = Math.min(dp[0][i-1] + cost[i], dp[0][i-2] + cost[i]);
        }

        dp[1][0] = 0;
        dp[1][1] = cost[1];
        dp[1][2] = dp[1][1] + cost[2];

        for(int i =3;i < cost.length;i++){

          dp[1][i] = Math.min(dp[1][i-1] + cost[i], dp[1][i-2] + cost[i]);
        }

        for(int i =0;i < 2;i++){
            for(int j = 0;j < cost.length;j++){
                System.out.print(dp[i][j] + "  ");
            }
            System.out.println();
        }
        return Math.min(Math.min(dp[0][cost.length - 1], dp[0][cost.length - 2]), Math.min(dp[1][cost.length - 1], dp[1][cost.length - 2]));
    }


    public int minCostClimbingStairsII(int[] cost) {

        int n = cost.length;
        int [] dp = new int[n + 1];
        for(int i = 2;i <= n;i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }






    private static int [][] direction = {{0, 1},{1, 0},{0, -1},{-1, 0}};
    /**
     * 695. 岛屿的最大面积
     * @param grid
     * @return
     */
    public static int maxAreaOfIsland(int[][] grid) {

        if(grid == null || grid.length == 0){
            return 0;
        }



        int area = 0;
        for(int i = 0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                area = Math.max(depthFirstMaxAreaOfIsland(grid, i, j), area);
            }
        }
        System.out.println(area);
        return area;
    }

    public static int depthFirstMaxAreaOfIsland(int [][] grid, int row, int col){

        System.out.println("row:" + row + "   col: " +  col);
        if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length){
            return 0;
        }
        if(grid[row][col] == 0){
            return 0;
        }

        grid[row][col] = 0;
        int area = 1;
        for(int i =0;i < 4;i++){
            //row = row+direction[i][0];
            //col = col + direction[i][1];
            area += depthFirstMaxAreaOfIsland(grid, row+direction[i][0], col + direction[i][1]);
        }
        return area;
    }

    /**
     *
     * 213. 打家劫舍 II
     * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。
     * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     *
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
     * 链接：https://leetcode-cn.com/problems/house-robber-ii
     *
     * 最后的输出取决于第一间方是否闯入，若第一间房闯入，则最后一件房不能闯入；若第一件房未闯入，则最后一件房都可以
     * @param nums
     * @return
     */
    public static int robII(int [] nums){

        if(nums == null || nums.length == 0){
            return 0;
        }
        if(nums.length == 2){
            return Math.max(nums[0], nums[1]);
        }
        //dp表示第一件房闯入的动态方程，dp[0][0] = nums[0],第二间房则一定不能闯入，从第三间房间开始可闯入、可不闯入，思路跟robI相同
        int [][]dp = new int[nums.length][2];
        //dp2表示第一间房未闯入， dp[0][0] = 0, dp[0][1]= 0, 第二间房闯入、不闯入都可以。
        int [][]dp2 = new int[nums.length][2];
        dp[0][0] = nums[0];
        dp[0][1] = 0;

        dp[1][1] = nums[0];
        for(int i = 2;i < nums.length;i++){
            dp[i][0] = dp[i-1][1] + nums[i];
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]);
        }

        for(int i= 1;i < nums.length;i++){
            dp2[i][0] = dp2[i-1][1] + nums[i];
            dp2[i][1] = Math.max(dp2[i-1][0], dp2[i-1][1]);
        }
        System.out.println("dp1");
        for(int i =0;i < nums.length;i++){
            System.out.print(dp[i][0] + "   " + dp[i][1]);
            System.out.println();
        }

        System.out.println("dp2");
        for(int i =0;i < nums.length;i++){
            System.out.print(dp2[i][0] + "   " + dp2[i][1]);
            System.out.println();
        }

        return Math.max(dp[nums.length - 1][1], Math.max(dp2[nums.length - 1][0], dp2[nums.length - 1][1]));
    }

    /**
     * 198. 打家劫舍
     * Simple
     * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
     * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
     *
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
     * 链接：https://leetcode-cn.com/problems/house-robber
     * @param nums
     * @return
     */
    public static int rob(int[] nums) {

        if(nums == null || nums.length == 0){
            return 0;
        }
        //dp[i][0] 第i天闯入的最大收益， dp[i][1] 第i天不闯入的最大收益
        //dp[i][0] = dp[i-1][1] + nums[i]
        int [][] dp = new int[nums.length][2];
        dp[0][0] = nums[0];
        dp[0][1] = 0;
        for(int i = 1; i < nums.length;i++){
            dp[i][0] = dp[i-1][1] + nums[i];
            dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]);

        }
        for(int i =0;i < nums.length;i++){
            System.out.print(dp[i][0] + "   " + dp[i][1]);
            System.out.println();
        }
        return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
    }

    /**
     * 188. 买卖股票的最佳时机 IV
     * k次操作最佳收入
     * @param prices
     * @param k
     * @return
     */
    public static int maxProfitKOperation(int [] prices, int k){

        if(k <= 0 || prices == null || prices.length <= 1){
            return 0;
        }
        int len = prices.length;
        if(k > len/2){
            return maxProfitMoreOperations2(prices);
        }
        //dp[k][0]: 第k次买股票， dp[k][1]:第k次卖股票
        int [][] dp = new int[k][2];
        for(int i =0;i < k;i++){
            dp[i][0] = Integer.MIN_VALUE;
        }
        for(int price : prices){
            dp[0][0] = Math.max(dp[0][0], -price);
            dp[0][1] = Math.max(dp[0][1], dp[0][0] + price);
            for(int i = 1;i < k;i++){
                dp[i][0] = Math.max(dp[i][0], dp[i-1][1] - price);
                dp[i][1] = Math.max(dp[i][1], dp[i][0] + price);
            }
        }
        return dp[k-1][1];
    }



    /**
     * 123. 买卖股票的最佳时机 III
     * 股票买卖最多2次操作
     * @param prices
     * @return
     */
    public static int maxProfixTwoOperation(int [] prices){

        if(prices == null || prices.length <= 1){
            return 0;
        }
        int firstBuy = Integer.MIN_VALUE, firstSell = 0;
        int secondBuy = Integer.MIN_VALUE, secondSell = 0;
        for(int price : prices){

            firstBuy = Math.max(firstBuy, -price);
            firstSell = Math.max(firstBuy + price, firstSell);
            secondBuy = Math.max(secondBuy, firstSell - price);
            secondSell = Math.max(secondBuy + price, secondSell);
        }
        return secondSell;

    }

    /**
     * . 买卖股票的最佳时机 I
     * 股票最多一次买卖
     * @param prices
     * @return
     */
    public static int maxProfitOneOperation(int[] prices) {

        if(prices == null || prices.length <= 1){
            return 0;
        }

        int minPrice = prices[0];
        int maxProfit = 0;
        for(int i = 1;i < prices.length;i++){
            int tmpPrice = prices[i];
            int tmpProfit = tmpPrice - minPrice;
            maxProfit = tmpProfit >= maxProfit ? tmpProfit : maxProfit;
            minPrice = tmpPrice <= minPrice ? tmpPrice : minPrice;
        }
        return maxProfit;
    }

    /**
     * @author zlx
     * @Description 剑指 Offer 63. 股票的最大利润 middle
     * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
     *
     *
     *
     * 示例 1:
     *
     * 输入: [7,1,5,3,6,4]
     * 输出: 5
     * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
     * 示例 2:
     *
     * 输入: [7,6,4,3,1]
     * 输出: 0
     * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     * @Date 2020-12-25
     * @Param [prices]
     * @return int
     **/
    public int maxProfitI(int[] prices) {

        if(prices == null || prices.length <= 1){
            return 0;
        }

        Integer max = 0;
        for(int i = 1;i < prices.length;i++){
            for(int j = i-1;j >= 0;j--){
                max = Math.max(prices[i] - prices[j], max);
            }
        }

        return max;
    }


    /**
     * 122. 买卖股票的最佳时机 II
     * 股票可多次买卖
     * @param prices
     * @return
     */
    public static int maxProfitMoreOperations(int[] prices) {

        if(prices == null || prices.length <= 1){
            return 0;
        }
        int [][] profit = new int [2][prices.length];
        profit[0][0] = 0;
        profit[1][0] = 0 - prices[0];
        //dp[1][i] 第i天买入股票的价格， dp[0][i] 第i天卖出股票的价格
        for(int i = 1;i < prices.length;i++){
            profit[0][i] = Math.max(profit[1][i-1] + prices[i], profit[0][i-1]);
            profit[1][i] = Math.max(profit[0][i-1] - prices[i], profit[1][i-1]);
        }
        /*for(int i =0;i < prices.length;i++){
            System.out.print(profit[0][i]);
            System.out.print("     ");
        }
        System.out.println();
        for(int i =0;i < prices.length;i++){
            System.out.print(profit[1][i]);
            System.out.print("     ");
        }
        System.out.println();*/
        return profit[0][prices.length - 1];
    }


    /**
     * 122. 买卖股票的最佳时机 II
     * 股票可多次买卖
     * 方法2
     * @return
     */
    public static int maxProfitMoreOperations2(int [] prices){
        int result = 0;
        for(int i = 1;i < prices.length;i++){

            result += Math.max(0, prices[i] - prices[i-1]);

        }
        return result;
    }
}
